[백준] 17616. 등수 찾기

문제 링크

[백준] 17616. 등수 찾기

풀이 과정

두 개의 인접 리스트를 만들어, BFS 탐색을 각각 진행했습니다.

ArrayList<Integer>[][] adj = new ArrayList[2][N + 1];

2차원 배열의 인접 리스트에 간선 정보를 저장했습니다.

adj[0]은 순방향, 즉 점수가 낮은 학생에서 점수가 높은 학생 으로 방향있는 간선이 그려지며, adj[1] 은 역방향, 즉 점수가 높은 학생에서 낮은 학생으로 간선이 이어집니다.

그래프를 두 번 만드는 이유는 아래 그림을 통해 설명하겠습니다.

왼쪽이 adj[0]에 저장된 간선 정보로 그린 순방향 그래프, 오른쪽이 adj[1]에 저장된 간선 정보로 그린 역방향 그래프입니다.

각 그래프를 K를 시작으로 BFS 탐색을 하면, 위와 같이 표시할 수 있습니다.

먼저, 왼쪽 순방향 그래프는 정점 1을 시작으로 더이상 진행할 곳이 없으며, 이는 1번 학생 위로 아무도 없다는 것을 의미합니다.

반대로, 오른쪽 역방향 그래프는 정점 1을 시작으로 정점 3, 4, 5로 갈 수 있으며, 이는 1번 학생 밑으로 3명이 있다는 것을 의미합니다.

즉, 인접리스트 두 개를 이용해, 순방향 탐색으로는 K번 학생 위에 몇 명이 있는지를 확인해 가능한 가장 높은 등수(U)를 구하며, 역방향 탐색으로는 K번 학생 아래에 몇 명이 있는지를 확인해 가능한 가장 낮은 등수(V)를 구할 수 있습니다.

코드

import java.util.*;

public class Main {
    static int N, M, K;
    static ArrayList<Integer>[][] adj;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        K = sc.nextInt();
        adj = new ArrayList[2][N + 1];
        visit = new boolean[N + 1];

        for (int i = 0; i < 2; i++) {
            for (int j = 1; j <= N; j++) {
                adj[i][j] = new ArrayList<>();
            }
        }

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();

            adj[0][b].add(a);
            adj[1][a].add(b);
        }

        int U = bfs(0);
        Arrays.fill(visit, false);
        int V = N - bfs(1) + 1;

        System.out.println(U + " " + V);
    }

    static int bfs(int dir) {
        Queue<Integer> q = new LinkedList<>();
        visit[K] = true;
        q.add(K);
        int cnt = 0;

        while (!q.isEmpty()) {
            int now = q.poll();
            cnt++;

            for (int next : adj[dir][now]) {
                if (!visit[next]) {
                    visit[next] = true;
                    q.add(next);
                }
            }
        }

        return cnt;
    }
}