[백준] 9470 Strahler 순서

1. 문제

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

9470번: Strahler 순서

2. 접근방법

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

14567번: 선수과목 (Prerequisite)

요 문제랑 얼추 비슷한 문제

 

현재 노드의 Strahler 순서를 알려면 부모의 순서를 모두 알아야 하므로

모든 부모의 Strahler 순서가 정해진 다음에 내 순서를 찾아야 한다.

 

그렇기 때문에 현재 노드의 부모 노드와 자식노드 모두 가지고 있어야 한다.

 

나는 HashSet을 이용해 부모노드를 저장해 두고

순서를 알게된 부모는 Set에서 제거하여 남은 부모가 없어지면 내 순서를 찾는 방식으로 풀이 했다.

 

1. parent, child, order 배열 생성

2. 입력에서 부모와 자식 모두 저장

3. 루트 노드들의 순서 1로 저장

4. bfs를 돌리며 현재 노드의 자식들 부모Set에서 현재 노드 삭제

5. 삭제 하면서 지금까지 부모들의 순서 중 가장 큰 값과 개수를 저장

5. 현재 노드를 부모 Set에서 제거 후 남은 부모가 없으면 해당 자식노드 que에 추가

6. 저장해 놓은 부모들 중 가장 큰 값과 개수를 가지고 현재 노드의 순서 입력

7. 모든 노드를 돌 때까지 반복

3. 자바 코드

package backjoon;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.List;
import java.util.Queue;
import java.util.*;

public class P9470strahler {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int K = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int P = Integer.parseInt(st.nextToken());
            HashSet<Integer> parent[] = new HashSet[M + 1];
            List<Integer> child[] = new ArrayList[M + 1];
            Point count[] = new Point[M + 1];
            int order[] = new int[M + 1];
            for (int i = 0; i <= M; i++) {
                parent[i] = new HashSet<>();
                child[i] = new ArrayList<>();
                count[i] = new Point(0, 0);
            }
            for (int i = 0; i < P; i++) {
                st = new StringTokenizer(br.readLine());
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());
                parent[B].add(A);
                child[A].add(B);
            }
            Queue<Integer> que = new LinkedList<>();
            for (int i = 1; i < M + 1; i++) {
                if (parent[i].isEmpty()) {
                    order[i] = 1;
                    que.add(i);
                }
            }
            while (!que.isEmpty()) {
                int now = que.poll();
                for (int chil : child[now]) {
                    parent[chil].remove(now);
                    if (count[chil].x < order[now]) {
                        count[chil].x = order[now];
                        count[chil].y = 1;
                    } else if (count[chil].x == order[now]) {
                        count[chil].y++;
                    }

                    if (parent[chil].isEmpty()) {
                        order[chil] = count[chil].y == 1 ? count[chil].x : count[chil].x + 1;
                        que.add(chil);
                    }
                }
            }
            System.out.println(K + " " + order[M]);
        }
    }
}

4. 마치며

이런 유형 문제도 코테에 가끔 나오는 듯