[백준] 17616번 : 등수 찾기

17616번: 등수 찾기

---

[DFS]

등수를 알고싶은 x번째 정점에서 DFS를 2번 수행 해야하므로 인접리스트를 2개 만든다.

입력으로 A B가 주어졌을 때,

list[B][0].add(A),

list[A][1].add(B)

처럼 2개의 인접리스트를 만들면 된다.

 

DFS의 내부는 간단하다. 기본적으로 int rank = 1을 갖고 인접리스트를 돌며 방문하지 않은 정점을 돌며 계속 그 값을 더해나간다.

    static int DFS(int x, int idx){

        visit[x] = true;
        int rank = 1;

        for(int next:list[x][idx])
            if(!visit[next])
                rank += DFS(next, idx);

        return rank;
    }

이제 x의 가장 높은 등수, 가장 낮은 등수를 구하면 되는데 구하는 방법은 다음과 같다.

        int u = DFS(x, 0); //가장 높은 등수
        
        visit = new boolean[100001];
        
        int v = n - DFS(x, 1) + 1; //가장 낮은 등수

다음은 문제의 마지막 예시 입력에 대한 풀이이다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static List<Integer>[][] list = new ArrayList[100001][2];
    static boolean[] visit = new boolean[100001];

    static int DFS(int x, int idx){

        visit[x] = true;
        int rank = 1;

        for(int next:list[x][idx])
            if(!visit[next])
                rank += DFS(next, idx);

        return rank;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++) {
            list[i][0] = new ArrayList<>();
            list[i][1] = new ArrayList<>();
        }

        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());

            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            list[v2][0].add(v1); //가장 높은
            list[v1][1].add(v2); //가장 낮은
        }

        int u = DFS(x, 0);
        int v = n - DFS(x, 1) + 1;

        System.out.println(u + " " + v);
    }
}
/*11 10 1
1 2
2 6
6 7
7 8
3 2
4 2
5 2
9 1
10 5
11 10*/