백준 9479, Strahler 순서(java)

문제 설명

강은 간선으로 물이 흐르는 방향은 간선의 방향이 된다. 또한 노드는 호수나 샘처럼 강이 시작하는 곳, 합쳐지거나 나누어지는 곳, 바다와 만나는 곳이다. 

 

이때 Stracher는 강의 근원인 노드인 경우는 1, 나머지 노드는 그 노드로 들어오는 강의 순서 중 가장 큰 값을 i라고 했을 때 i가 1개이면 i, 2개 이상이면 i+1이다.

 

이때 m은 바다로 이어지는 노드라고 할 때 m의 Strhler를 구하라.

 

https://www.acmicpc.net/problem/9470

9470번: Strahler 순서

문제 풀이

일단 강의 근원인 노드가 아닌 부분부터 시작해서 다른 노드로 움직여야 하는 의무적인 방향성이 존재한다. 이는 위상 정렬이다. 하지만, 여기서 중요한 건 우리는 단순한 위상 정렬이 아니라 Strahler를 구해줘야 한다는 것이다. 그렇다면 이는 어떻게 구할까?

 

나는 각 노드마다 Strahler를 저장할 수 있는 answer 배열을 만들어 줬다. 그리고 강이 시작되는 노드들에는 문제에 나왔던 것처럼 전부 1을 넣어줬다. 

 

그리고 위상 정렬을 해주는데, 이때 중요한 건 next노드의 i들을 어딘가에 저장해야 한다는 것이다. next 노드에서 오는 i들을 전부 어딘가에 저장한 다음 제일 큰 i를 구해서 next가 시작 노드가 됐을 때 next의 answer을 갱신해주는 방식이다.

 

그렇기 때문에 나는 dist를 2차원 list로 만들어서 next의 밑에다가 i들을 일단 저장해줬다. 그리고 next의 pre가 0이 되어 더이상 먼저 방문해야 하는 노드가 존재하지 않는다면 dist의 next에 있는 리스트를 내림차순 정렬해준다. 그리고 문제에 나왔던 조건대로 만일 next의 i 리스트 크기가 1이라 하나 밖에 없다면 next의 Strahler는 첫 번째 값으로 넣어준다. 그렇지 않고 첫 번째 i와 두 번째  i가 같아 i가 2개 이상 존재한다면 Strahler에는 i에다가 1을 더해준다. 최댓값 i가 하나만 있다면 Strahler에는 첫 번째 값을 넣어준다.

 

그리고 마지막으로 바다와 연결된 노드 m의 answer 값을 k와 나란히 출력하면 된다.

 

이 문제는 위상 정렬을 이용하지만 동시에 각 노드의 i를 저장할 필요가 있는 문제였다.

코드

java

import java.util.*;
import java.io.*;


public class Main {

    public static int T;

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

        T = Integer.parseInt(br.readLine());

        for (int i=0; i<T; i++) {
            st  = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());
            List<List<Integer>> list = new ArrayList<>();
            int[] pre = new int[m+1];
            int[] answer = new int[m+1];
            List<List<Integer>> dist = new ArrayList<>();
            Queue<Integer> queue = new LinkedList<>();

            for (int j=0; j<=m; j++) {
                list.add(new ArrayList<>());
                dist.add(new ArrayList<>());
            }

            for (int j=0; j<p; j++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                list.get(a).add(b);
                pre[b]++;
            }

            for (int j=1; j<=m; j++) {
                if (pre[j] == 0) {
                    answer[j] = 1;
                    queue.add(j);
                }
            }

            while(!queue.isEmpty()) {
                int current = queue.poll();

                for (int next : list.get(current)) {
                    pre[next]--;
                    dist.get(next).add(answer[current]);

                    if (pre[next] == 0) {
                        Collections.sort(dist.get(next), Collections.reverseOrder());
                        if (dist.get(next).size() == 1) {
                            answer[next] = dist.get(next).get(0);
                        } else {
                            if (dist.get(next).get(0) == dist.get(next).get(1)) {
                                answer[next] = dist.get(next).get(0) + 1;
                            } else {
                                answer[next] = dist.get(next).get(0);
                            }
                        }
                        queue.add(next);
                    }
                }
            }

            System.out.println(k + " " + answer[m]);

        }

    }

}