백준 9470 Strahler 순서[Java]

solved.ac = 골드 3

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

9470번: Strahler 순서

 

---

1. 접근

 

주어진 그래프를 위상 정렬을 하되 문제 속 조건인 Strahler의 순서를 구하는 조건을 참고하여 푸는 문제입니다.

 

입력의 간선 정보로 각 노드의 진입 차수를 저장하고 방문시마다 감소시키며 순서를 카운트하고 가장 큰 순서를 출력하면 되는데 기본 위상 정렬에서 조건을 조~~ 금 추가했다고 바로 오랫동안 삽질했습니다...

 

기본적으로 위상 정렬을 수행하는 코드에 스트롤러 순서를 정하는 부분만 추가하면 되는데 방법은 문제에서 대놓고 제시하고 있습니다.

 

올바르게 이해한지는 모르겠으나 정답은 맞았으니 이해한 그대로 간단하게 생각하고 밑에 두 가지에 집중하여 문제를 풀었습니다.

• 강의 근원을 제외한 노드들은 들어오는 노드들의 순서 중 최대 순서를 따른다.
• 단, 동일 순서(i)에서 들어오는 노드가 여러 개 일 경우 최대 순서에서 하나 증가시킨다.(i + 1)

 

이해를 위해 예제 입력을 그림으로 설명하겠습니다.

 

먼저 최초 강의 근원만 있는 상태에서 시작하면 다음과 같습니다.

 

 

그럼 위상 정렬 수행을 위해 진입 차수가 0인 1, 2, 6이 큐에 들어가고 1, 2에서 3을 먼저 방문한다고 가정하겠습니다.

(어디를 먼저 방문하건 상관은 없습니다)

 

3의 입장에서 살펴보자면

 

1에서 3으로 방문 시 첫 간선이기에 1의 순서를 따른다.

2에서 3으로 방문시 두 번째 간선이고 2의 순서 역시 1이기에 순서는 변하지 않는다.

 

단, 여기서 1의 순서를 가진 노드가 1과 2로 여러 개이기 때문에 스트롤러 순서를 구하는 방법에 의해 하나 증가하여 2가 된다.

 

이 방법대로 모든 노드를 방문하면 문제 속 그림이 완성된다.

 

---

2. 풀이

 

변수 세팅

static int K, M, P;
static int[] indeg, order, maxCnt;
static ArrayList<Integer>[] graph;
public static void main(String[] args) throws IOException {
    int T = Integer.parseInt(br.readLine());
    while (T --> 0) {
        st = new StringTokenizer(br.readLine());
        K = Integer.parseInt(st.nextToken()); // 테스트 케이스 번호
        M = Integer.parseInt(st.nextToken()); // 노드의 수
        P = Integer.parseInt(st.nextToken()); // 간선의 수
        indeg = new int[M + 1]; // 각 노드의 진입 차수의 수
        maxCnt = new int[M + 1]; // 해당 노드로 들어오는 강의 수
        order = new int[M + 1]; // 진입 순서

        graph = new ArrayList[M + 1];
        for(int i = 1; i <= M; i++) graph[i] = new ArrayList<>();
        for (int i = 1; i <= P; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            indeg[y]++;
        }
        solution();
    }
    System.out.println(sb.toString());
}

 

탐색

static void solution() {
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 1; i <= M; i++) {
        // 진입 차수가 0인 건을 미리 add한다.
        if (indeg[i] == 0) {
            queue.add(i);
            // 강의 근원은 1로 한다.
            order[i]++;
            maxCnt[i]++;
        }
    }

    int answer = 0;
    while(!queue.isEmpty()) {
        int x = queue.poll();
        if (maxCnt[x] >= 2) order[x]++; // 들어오는 강이 2개 이상이면 순서를 증가시킨다.
        answer = Math.max(answer, order[x]); // 정답 갱신.
        for (int y : graph[x]) {
            indeg[y]--; // 간선 정보를 삭제한다.
            if (indeg[y] == 0) queue.add(y); // 해당 노드로 향하는 간선은 없다.
            if (order[y] == order[x]) maxCnt[y]++; // 동일 순서에서 또 방문했다.
                // 스트랄러 순서는 들어오는 순서 중 최대값으로 한다.
            else if (order[y] < order[x]) {
                order[y] = order[x];
                maxCnt[y] = 1;
            }
        }
    }
    sb.append(K).append(' ').append(answer).append('\n');
}

---

3. 전체 코드