순위 (Java)

📌 문제 설명

순위 - 프로그래머스

• n명의 선수가 1대1 경기 결과를 기반으로 순위를 결정할 수 있는 선수 수를 구하는 문제입니다.
• A 선수가 B 선수를 이겼다면, A는 B보다 순위가 높다.
• 하지만 경기 결과만 주어졌을 때, 순위를 확실하게 알 수 있는 선수만 카운트해야 함.

---

💡 접근 방식

✔ 모든 선수에 대해 BFS 탐색을 수행하여 경기 결과를 추적
✔ 특정 노드(선수)의 "들어오는 방향의 총 개수 + 나가는 방향의 총 개수"가 n-1이면 순위를 결정 가능
✔ 이를 활용하여 순위를 결정할 수 있는 선수 수를 구하는 방식

---

🔹 문제 해결 아이디어

1. 그래프를 구성 (양방향 탐색)
   • connInfo[cur[1]].add(cur[0]); → 이긴 선수 → 진 선수 연결
2. 모든 노드(선수)에서 BFS 수행
   • 이긴 경기(outCnt)와 진 경기(inCnt) 개수를 계산
3. 각 노드에서 inCnt[i] + outCnt[i] == n-1이면 순위 결정 가능

---

📝 코드 구현

import java.util.*;

class Solution {
    int N;
    List<Integer>[] connInfo;
    int[] inCnt;
    int[] outCnt;

    public int solution(int n, int[][] results) {
        N = n + 1;
        inCnt = new int[N];
        outCnt = new int[N];

        // 그래프 초기화
        connInfo = new List[N];
        for (int i = 0; i < N; i++) {
            connInfo[i] = new ArrayList<>();
        }

        // 경기 결과 입력 (진 선수 → 이긴 선수로 그래프 구성)
        for (int[] cur : results) {
            connInfo[cur[1]].add(cur[0]);
        }

        // 모든 선수에 대해 BFS 실행
        for (int i = 1; i < N; i++) {
            bfs(i);
        }

        // 순위를 확정할 수 있는 선수 수 계산
        int answer = 0;
        for (int i = 1; i < N; i++) {
            if (inCnt[i] + outCnt[i] == n - 1) answer++;
        }
        return answer;
    }

    private void bfs(int start) {
        boolean[] visited = new boolean[N];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;
        int outSum = 0;

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int next : connInfo[cur]) {
                if (visited[next]) continue;
                visited[next] = true;
                inCnt[next]++; // 해당 선수가 이긴 횟수 증가
                outSum++; // 현재 선수가 진 횟수 증가
                queue.add(next);
            }
        }
        outCnt[start] += outSum;
    }
}

---

🧐 코드 분석

변수	의미
connInfo	이긴 선수 → 진 선수 연결 정보 저장
inCnt[i]	해당 선수가 진 경기 개수
outCnt[i]	해당 선수가 이긴 경기 개수
visited	BFS 방문 여부 확인
queue	BFS 탐색을 위한 큐

🔹 시간복잡도

• O(N^2): 모든 선수에 대해 BFS (O(N) * O(N))
• 그래프 탐색 문제에서 최적의 풀이

---

🎯 예제 실행

입력 예시

int n = 5;
int[][] results = {
    {4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}
};

BFS 탐색 과정

선수	이긴 경기 (outCnt)	진 경기 (inCnt)	확정 가능 여부
1	1	0	❌
2	1	3	✅
3	1	1	✅
4	2	0	✅
5	0	1	❌

✅ 출력값: 2

---

🚀 결론 및 정리

✔ 그래프 탐색을 통해 선수별 경기 결과를 분석
✔ BFS를 활용하여 경기 기록을 탐색하고 승패 개수를 저장
✔ 각 선수의 (이긴 경기 수 + 진 경기 수 == n-1) 여부를 체크하여 순위 결정 가능