[프로그래머스] 순위 Java 풀이

PROBLEM

https://programmers.co.kr/learn/courses/30/lessons/49191

SOLUTION

이 문제에서 핵심은 선수의 순위가 결정되는 조건을 찾는 것이다. 문제 속 제한사항도 크기가 작기 때문에 이 조건을 찾고 구현한다면 해결할 수 있는 문제라고 생각했다. 그 조건이 아래와 같다.

순위가 결정되는 선수는 다른 모든 선수와의 승패가 결정되어야 한다.

이를 구현하기 위해서 그래프를 이용했고 문제의 예시를 통해서 차근차근 살펴보자.

그래프
그래프
그래프
4번 노드가 도달가능한 곳
그래프
2번 노드가 도달가능한 곳

좌측 그림은 문제 속 예시의 경기 결과를 그래프의 간선으로 보고, 유향그래프를 그린 것이다. 위에 있을수록 높은 순위를 가지는데, 2번과 5번은 순위가 결정되지만 1, 3, 4번은 관계가 불확실하다. (그림으로는 이해하기 힘들 수 있지만, 이미 이 사실은 알고있을거라 생각한다.)

이 유향그래프에서 4번이 도달가능한 노드를 보자. 4번은 2, 3, 5번에 도달할 수 있지만, 1번에는 도달할 수 없다. (가운데 그림)

그렇다면 2번 노드를 보자. 2번은 5번에만 도달할 수 있다. (우측 그림)

이쯤에서 이 사실이 무엇을 의미하는지 느낌이 왔는가? 경기 결과를 간선으로 표현했더니, 어떤 노드에서 도달가능한 노드는 그 노드(선수)가 이길 수 있는 노드(선수)를 의미한다. 가운데 그림에서 4번이 5번에 도달하려면 2번을 거쳐서 가는데, 이는 4번이 2번을 이기고, 2번이 5번을 이기니까 4번이 5번을 이길 수 있다는 것을 의미한다.

그래서, 해당 그래프의 각각의 노드로부터 BFS를 실행하여 도달가능한 노드를 표시(visited[][])한다. 그렇다면 각 노드(선수)가 이길 수 있는 노드(선수)가 무엇인지 알 수 있다.

다시 조건을 상기시켜보자면, “다른 모든 사람과의 승패가 결정되어야 한다.” 방금 구해낸 것은, 승리에 대해서만 표시를 한 것이다. A 선수가 B 선수를 이겼다(1)면 B 선수는 A 선수에게 졌다(2)는것을 의미하므로, (1)과 (2) 둘 중에 하나의 결과만 있더라도 상관이 없다. BFS를 끝낸 후에 visited[][]를 확인하는데 visited[i][j]와 visited[j][i] 둘 다 결과가 없어야 승패를 결정할 수 없는 것이다. (21번 라인)

따라서, 순서는 다음과 같다.

  1. 경기 결과를 간선으로 보고, 그래프를 만든다. (인접행렬 이용)
  2. 각 노드별로 BFS를 실행한다. 실행한 후에 각 노드별로 도달가능한 노드를 표시한다. (visited[][])
  3. vistied[][]를 확인하는데, 어떤 노드 i에서 다른 노드 j의 승패결과가 있는지 확인하고 모든 j에 대해서 결과가 존재하는 노드의 개수를 센다.

SOURCE CODE (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

import java.util.*;

public class Solution {
  boolean[][] visited;

  public int solution(int n, int[][] results) {
    int answer = 0;

    int[][] adjMatrix = new int[n][n];

    for (int[] result : results) {
      adjMatrix[result[0]-1][result[1]-1] = 1;
    }

    visited = new boolean[n][n];
    bfs(adjMatrix, n);

    for (int i=0; i<n; i++) {
      boolean hit = true;
      for (int j=0; j<n; j++) {
        if (!visited[i][j] && !visited[j][i])
          hit = false;
      }
      if (hit)  answer++;
    }

    return answer;
  }

  private void bfs(int[][] adjMatrix, int n) {
    for (int i=0; i<n; i++) {

      boolean[] visitedTmp = new boolean[n];
      Queue<Integer> queue = new LinkedList<>();

      visitedTmp[i] = true;
      queue.add(i);

      while(!queue.isEmpty()) {
        int polled = queue.poll();
        for (int j=0; j<n; j++) {
          if (!visitedTmp[j] && adjMatrix[polled][j] > 0) {
            visitedTmp[j] = true;
            queue.add(j);
          }
        }
      }

      for (int j=0; j<n; j++)
        if (visitedTmp[j])
          visited[i][j] = true;

    }
  }
}

OFF THE RECORD

다른 사람들의 풀이를 보면 플로이드워샬 알고리즘을 사용한 코드들이 많았다. 이 역시 마찬가지로 도달가능한지를 파악하기 위함이었고, 시간복잡도는 비슷해보였다. 하지만 코드가 훨씬 깔끔했다.

댓글 남기기

관련있는 다른 게시글