[Java] 플로이드-워셜, DFS | 백준 2458 키 순서

https://www.acmicpc.net/problem/2458

 
접근 방법
 
첫접근(실패)
문제 유형을 보지 않고 풀어보았을 때 일차원 테이블을 만들고
관계가 주어질 때, a > b인 경우, 배열에서 b보다 큰 학생 수를 a의 위치에 누적하여 기록
만약 이미 누적된 값이 크다면 해당 관계는 무시함
배열의 최종 값이 유일(unique)하다면, 해당 학생의 순위를 알 수 있다.
하지만 이 방법은 간접 관계 확인 불가 등의 이유로 실제 순위를 보장하기 충분하지 않았다.
 
첫번째 방법(플로이드-워셜) 
문제 유형이 플로이드-워셜인 것을 확인한 뒤 풀어보았다.
처음엔 int[] 배열로 풀이했다가 자신보다 큰 사람을 true로 체크하는 boolean[] 배열로 바꾸어서 코드를 더 간결하게 바꿀 수 있었다.

int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

boolean[][] H = new boolean[N][N];

for(int i=0; i < M; i++){
    st = new StringTokenizer(br.readLine());
    int u1 = Integer.parseInt(st.nextToken());
    int u2 = Integer.parseInt(st.nextToken());

    H[u1-1][u2-1] = true;
}

아래와 같이 플로이드-워셜 알고리즘을 적용한다.
k를 기준으로 i 와 k 의 대소 관계(i의 키<j의 키)가 정해진다면 H[i][j] = true로 설정한다.

for(int k=0; k < H.length; k++) {
    for (int i = 0; i < H.length; i++) {
        if(i == k) continue;
        for (int j = 0; j < H.length; j++) {
            if(H[i][k] && H[k][j]) {
                H[i][j] = true;
            }
        }
    }
}

자신이 키가 몇 번째인지 알 수 있는 학생은 자신보다 몇명이 큰지, 자신보다 몇명이 작은지 정확히 셀 수 있는 학생이다.
N명의 학생이 존재한다면,i 기준으로 설명하면 H[i][j](자신보다 큰 학생 수) + H[j][i](자신보다 작은 학생 수) == N-1 이 되어야 위 조건을 만족시킬 수 있다.
이를 코드로 작성하면 아래와 같다.

int answer = 0;
for(int i=0; i < H.length; i++){
    int cnt=0;
    for(int j=0; j < H.length; j++){
        if(i==j) continue;
        if(H[i][j] || H[j][i]){
            cnt++;
        }
    }
    if(cnt==N-1) answer++;
}

최종적으로 answer가 우리가 원하는 정답이 된다.
 
이렇게 구현한 코드는 시간이 530ms 정도 대였다.
다른 사람들이 제출한 코드들 중 시간이 짧은 코드를 위주로 살펴보니 DFS로 접근한 풀이가 많아서 DFS로 다시 구현해보았다.
 
두번째 방법(DFS, 깊이우선탐색)
우선 DFS방식을 수행하기 위해 방문한 학생 체크를 위한 boolean 배열을 추가해준다.

H = new boolean[N][N];
visited = new boolean[N];

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    final int u1 = Integer.parseInt(st.nextToken());
    final int u2 = Integer.parseInt(st.nextToken());
    H[u1-1][u2-1] = true;
}

그리고 모든 학생에 대해 dfs를 호출한다. (방문된 학생 제외)

for (int i = 0; i < N; i++) {
    if (visited[i])
        continue;
    dfs(i);
}

dfs는 아래와 같이 구현된다. s를 시작 학생으로 두고, H[s][i](i가 s보다 키가 큼)이 true라면 i에 대해 dfs를 다시 호출한다.
이렇게 s 보다 큰 학생을 꼬리에 꼬리를 무는 방식으로 모두 찾은 뒤, H[s][j](s보다 큰 j)에 직전 dfs(i) 호출로 얻은 H[i][j](j가 i보다 큼)를true일 경우 갱신해준다.
if(H[s][i]) // i 가 s보다 큰 경우 (s < i) 
dfs(i) // i에 대해 i 보다 큰 경우 찾기 위해 다시 dfs 호출  => 그렇게 호출해서 i 행에 대한 모든 정보 갱신 (그렇게 i행에 누적된 true는 직전에 dfs(i)를 호출하게 만든 H[s][i] 즉 s행에 모두 true로 추가시켜야함.
 
H[s][j] = H[i][j]; // j가 i보다 크다면 j는 s보다도 크기 때문

public static void dfs(final int s) {
    if (visited[s])
        return;

    for (int i = 0; i < N; i++) {
        if (H[s][i]) {
            dfs(i);
            for (int j = 0; j < N; j++) {
                if(!H[s][j] && H[i][j]) {
                    H[s][j] = H[i][j];
                }
            }
        }
    }
    visited[s] = true;
}

이렇게 모든 학생에 대해 dfs 호출이 완료 되었다면 자신보다 큰 학생들에 대해 각 행에서 true들이 모두 갱신된 상태이다.
H[i][j] : i보다 j가 큼, H[j][i] : j보다 i가 큼 => 이 둘중하나는 true 여야 대소비교가 가능함
우리는 정확히 자신보다 크거나 작은 것을 아는 것이 중요하고 이것은 첫 번째 방법과 동일하게 N-1인지 체크하면 된다.

int answer = 0;
for (int i = 0; i < N; i++) {
    int sum = 0;
    for (int j = 0; j < N; j++) {
        if(H[i][j] || H[j][i]) sum++;
    }
    if (sum == N - 1)
        answer++;
}

 
 

 
플로이드워셜 알고리즘을 적용했을 때보다 dfs로 접근했을 때 더 좋은 성능을 보였는데 각 알고리즘의 복잡도를 고려해보면
 
방법 1 (플로이드-워셜)

• 3중 반복문을 사용
• 전체 시간 복잡도: O(N^3), 입력 데이터가 희소하더라도 O(N^3)로 고정
• 그래프의 밀집도(희소행렬, 밀집행렬)와 상관없이 모든 노드 쌍을 고려하는 플로이드워셜 알고리즘의 특성
• 공간 복잡도: O(N^2)

방법 2 (DFS)

• DFS를 N번 수행할 수 있으며, 각 DFS에서 최대 N개의 노드를 방문
• 전체 시간 복잡도: O(N * (N^2)) 
• 최선 : O(N^2)-H[s][i]가 모두 false라면 N번만 순회
• 최악 : O(N^3)
• 공간 복잡도: O(N^2) (인접 행렬) + O(N) (방문 배열)

위의 이유때문에 DFS 접근법이 이 문제에서 더 좋은 성능을 보인 것 같다. 평균적인 테스트 케이스가 DFS에 유리하지 않았을까 생각해본다.
 
DFS 접근법은 N이 작거나 그래프가 희소한 경우에는 좋은 성능을 보일 수 있지만, N이 커지거나 그래프가 밀집되었을 경우 DFS 호출마다 노드를 탐색하고 관계를 업데이트하는 과정에서 추가적인 오버헤드가 발생할 것이다.
반면, 플로이드워셜 알고리즘의 경우 중복 연산 없이 모든 노드 쌍을 일정하게 한 번씩만 확인하므로 과도한 오버헤드가 발생하는 경우는 적다.
 
 
 
느낀점 : 
dfs로 풀어보면서 느낀 것이 있는데, 문제를 풀기 위해 내가 직접 인접행렬을 손으로 그려보고 풀었을 때, DFS의 방법으로 풀고 있었다는 것이다.
하지만 정작 코드로 구현할 때는 전혀 다른 방법으로 접근했다. 내가 손으로 풀었을 때(본능적인?)풀이를 잘 케치하야 알고리즘으로 적절히 변환하는 감각을 키워야될거 같다.
또 플로이드워셜 알고리즘을 6일전에 처음 접했을 때 뭔가 애매하게 이해가 되지 않아 답답했는데, 지난 6일동안 최단경로 알고리즘에 대해 공부하고 관련된 문제 3,4개정도를 길게 고민해보니 점점 나의 것이 되는듯한 느낌이 들고 있다. 하루 한문제만 풀어도 깊게 고민을 해보는 것이 더 도움되는거 같아 코테에 자신감이 생길 때까지 꾸준히 매일 한문제씩 깊게 고민해봐야겠다.