[Algorithm: 그래프] 프로그래머스 <순위>

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=java

프로그래머스

문제 설명

n명의 선수가 있고, 일부 경기 결과만 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 구하는 문제다.

핵심 조건은 "실력이 좋으면 항상 이긴다"는 것이다. 즉 A가 B를 이기고, B가 C를 이기면 A는 C도 반드시 이긴다.

 

---

접근

어떤 선수의 순위를 정확히 알 수 있으려면, 그 선수와 나머지 모든 선수 간의 승패 관계가 전부 파악되어야 한다.

n명 중에서 자신을 제외한 n-1명 전원과 비교가 가능하면 순위를 확정할 수 있다.

그렇다면 주어진 경기 결과에서 직접 명시되지 않은 승패를 어떻게 유추할까?

예를 들어 A→B, B→C가 주어지면 A→C도 성립한다. 이 전이 관계(transitive relation)를 잘 처리하는 게 핵심이다.

 

 

풀이 1 - BFS

처음에는 winGraph 하나만 만들어서 BFS를 돌렸다. "A가 B를 이겼고, B가 C를 이겼으면 A는 C도 이긴다"는 전이 관계를 winGraph에서 BFS로 따라가면 어떤 선수가 간접적으로 이긴 선수까지 전부 셀 수 있을 것 같았다.

 

여기서 문제가 생겼다. 

이긴 관계만 추적하면 "내가 이긴 선수들의 수"는 알 수 있는데, "나에게 진 선수들의 수"를 알 방법이 없었다.

 

순위를 확정하려면 나보다 잘하는 선수 수 + 나보다 못한 선수 수가 n-1이어야 한다. 그래서 방향을 뒤집은 loseGraph를 따로 만들었다. A가 B를 이겼다면 loseGraph에는 B→A 간선을 추가했다. 이러면 선수 i에서 loseGraph BFS를 돌렸을 때 "i에게 직간접적으로 진 선수들"을 역방향으로 추적할 수 있다.

• winGraph: A가 B를 이겼을 때 A→B 간선
• loseGraph: A가 B를 이겼을 때 B→A 간선 (즉 B 입장에서 A에게 진 관계)

어떤 선수 i에 대해서

• winGraph BFS → i가 직접/간접적으로 이긴 선수 수
• loseGraph BFS → i에게 직접/간접적으로 진 선수 수 (= i가 진 선수들)

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        List<List<Integer>> winGraph = new ArrayList<>();
        List<List<Integer>> loseGraph = new ArrayList<>();
        
        for (int i=0; i<=n; i++) {
            winGraph.add(new ArrayList<>());
            loseGraph.add(new ArrayList<>());
        }
        
        for (int[] result : results) {
            int a = result[0];
            int b = result[1];
            
            winGraph.get(a).add(b);
            loseGraph.get(b).add(a);
        }
        
        for (int i=1; i<=n; i++) {
            int winCount = bfs(i, winGraph, n);
            int loseCount = bfs(i, loseGraph, n);
            
            if (winCount + loseCount == n - 1) {
                answer++;
            }
        }
           
        return answer;
    }
    
    int bfs(int start, List<List<Integer>> graph, int n) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        
        queue.offer(start);
        visited[start] = true;
        
        int count = 0;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    visited[next] = true;
                    count++;
                    queue.offer(next);
                }
            }
        }
        
        return count;
    }
}

 

 

---

 

 

풀이 2 - 플로이드-워셜

BFS로 풀고 나서 다른 사람 풀이를 보니 플로이드-워셜로 훨씬 짧게 푼 코드들이 있었다.

플로이드-워셜이란

플로이드-워셜은 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘이다. 핵심 아이디어는 중간 경유 노드 k를 활용하는 것이다.

i에서 j로 바로 가는 것보다, i→k→j로 가는 게 더 짧다면 갱신한다.

이걸 모든 k에 대해 반복하면 직접 연결되지 않은 노드 간의 경로도 전부 채워진다. 시간 복잡도는 O(n³)이다. 보통은 가중치 그래프에서 최단 거리를 구할 때 쓰지만, "중간을 경유해서 간접적인 관계를 전부 채운다" 는 것이다.

이 문제에 플로이드-워셜이 맞는 이유

이 문제를 다시 보면 아래 구조이다. 

A가 B를 이기고, B가 C를 이기면 A는 C도 이긴다

이게 정확히 플로이드-워셜의 경유 노드 논리와 일치한다. 

i가 k를 이기고, k가 j를 이기면 i는 j도 이긴다 → win[i][j] = true

최단 거리를 갱신하는 대신 승패 관계를 갱신하는 것뿐이다. 플로이드-워셜을 떠올리는 감각은 결국 "직접 연결되지 않은 관계를 중간을 통해 전부 채워야 한다" 는 상황에서 온다. 

 

 

이 조건을 3중 for문으로 전부 채워나가면 모든 선수 간 직간접적인 승패 관계를 구할 수 있다. 이후 각 선수 i에 대해 win[i][j] 또는 win[j][i] 중 하나라도 true인 j의 수가 n-1이면 순위를 확정할 수 있다.

import java.util.*;

class Solution {
    public int solution(int n, int[][] results) {
        int answer = 0;
        boolean[][] win = new boolean[n+1][n+1];
        
        for (int[] result : results) {
            int a = result[0];
            int b = result[1];
            win[a][b] = true;
        }
        
        for (int k = 1; k<=n; k++) {
            for (int i=1; i<=n; i++) {
                for (int j=1; j<=n; j++) {
                    if (win[i][k] && win[k][j]) {
                        win[i][j] = true;
                    }
                }
            }
        }
        
        for (int i=1; i<=n; i++) {
            int count = 0;
            
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                if (win[i][j] || win[j][i]) {
                    count++;
                }
            }

            if (count == n - 1) {
                answer++;
            }
        }
        
        return answer;
    }
}

시간 복잡도는 O(n³)이다. n이 최대 100이므로 100³으로 모든 테스트 케이스를 통과한다. 

 

---

BFS vs 플로이드-워셜

 

	BFS	플로이드-워셜
시간 복잡도	O(n * (n + E))	O(n³)
구현 복잡도	상대적으로 복잡	간결
핵심 아이디어	각 선수마다 탐색	중간 노드 경유해서 전체 갱신

그래프 문제를 풀 때 BFS가 훨씬 손에 익어서 자연스럽게 BFS로 먼저 접근했다. 실제로 BFS로도 풀리긴 했고, 틀린 접근도 아니다.

그런데 이 문제를 플로이드-워셜로 다시 풀어보면서 느낀 건, 노드 간 간접적인 관계를 전부 채워야 하는 구조에서는 BFS보다 플로이드-워셜이 훨씬 자연스럽게 맞아떨어진다.

BFS는 특정 노드 하나를 기준으로 탐색하는 방식이라, 이 문제처럼 모든 노드 쌍의 관계를 다 알아야 하는 경우엔 n번 반복해야 한다. 반면 플로이드-워셜은 처음부터 모든 쌍의 관계를 한 번에 채운다는 방향으로 설계된 알고리즘이라 코드도 짧고 흐름도 더 직관적이다.

앞으로 A→B→C처럼 중간 다리를 타고 관계가 전이되는 문제가 나오면, BFS보다 플로이드-워셜을 먼저 떠올려야겠다고 느꼈다.

 

 

 

---

 

정리

이 문제에서 핵심은 직접 명시된 결과 외에도 전이 관계로 승패를 유추할 수 있다는 것이다.

처음에는 BFS로 각 선수 기준으로 탐색해서 풀었는데, 풀고 나서 보니 플로이드-워셜이 이 문제 구조에 더 깔끔하게 맞았다.

플로이드-워셜은 보통 최단 거리 문제에서 자주 쓰이지만, 이렇게 간접적인 관계를 전부 채워야 하는 상황에서도 유용하다는 걸 느꼈다.