99클럽 코테 스터디 6일차 TIL [플로이드-워샬]

- 오늘의 학습 키워드 : 플로이드-워샬 알고리즘

 

[문제 이름 : 키 순서 (백준 2458, G4)]
문제 url : https://www.acmicpc.net/problem/2458

내가 작성한 코드는 아래와 같다.

import java.io.*;
import java.util.*;

public class Main {

    static int n, m;
    static boolean[][] dist;
    static final int MAXVAL = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        dist = new boolean[n+1][n+1];

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            // a가 b보다 키가 작다.
            dist[a][b] = true;
        }

        // 플로이드-워셜 알고리즘
        for(int k=1; k<=n; k++) { // 중간
            for(int i=1; i<=n; i++) { // 시작
                for(int j=1; j<=n; j++) { // 도착
                    // i가 k보다 작고, k가 j보다 작다면 i는 j보다 작다.
                    if(dist[i][k] && dist[k][j]) {
                        System.out.println("k: " + k + ", i: " + i + ", j: " + j);
                        dist[i][j] = true;
                    }
                }
            }
        }

        // 자신의 순서를 알 수 있는 학생 수
        int count=0;
        for(int i=1; i<=n; i++) {
            int known = 0;
            for(int j=1; j<=n; j++) {
                if(dist[i][j] || dist[j][i]) {
                    known++;
                }
            }

            // 자신을 제외한 모든 학생과의 관계를 알 수 있으면, 순서를 알 수 있음
            if(known == n-1) {
                count++;
            }
        }

        System.out.println(count);
    }
}

풀이 과정 (풀이 시간 : 35분)

각 정점마다 비교가 필요하므로, 플로이드-워샬 알고리즘이 바로 떠올랐다. 그러나 최대 개수가 500개인데, 플로이드-워샬 알고리즘은 O(N^3)의 시간복잡도를 가진다. 아마 비교 연산만 수행하기 때문에 통과되지 않은가 싶다. 문제를 풀면서 시간복잡도를 계산한 뒤, 어떤 자료구조를 선택할 지 파악하는 편인데, 이에 이렇게 풀이하는 게 맞는지 많이 고민했던 것 같다.

 

1. 2차원 배열을 생성해서, 키 값 정보를 저장한다. 이때, i,j가 있다면 키가 i보다 j가 크므로, 더 작은 키를의 정보를 true로 저장한다. (dist[i][j] = true로 저장한다.)

2. 실제 표를 그려보며 코드를 작성하면 이해를 빠르게 할 수 있다. 입력 1에서 3보다 4가 키가 크고, 4보다 2가 키가 크므로, 3보다 2가 키가 크다는 것을 알 수 있다. 이를 플로이드-워셜 알고리즘의 if문에서 구현하였다.
3. 각 학생이 본인이 몇 번째인지를 출력하는 게 아니라, 자신의 키 정보를 아는 학생을 출력하는 것이므로 복잡하게 생각할 필요 없다. 자신의 앞뒤로 키가 크고 작은 학생만 있는지 확인하면 된다.

4. 3번의 값과 자신을 제외한 모든 학생과의 관계의 값이 같다면, 순서를 알 수 있는 것이므로 count++를 진행했다.

내일은 금융권 하반기 자기소개서를 작성할 예정이다.