[백준 9470] Strahler 순서 (Swift)

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

하천계의 Strahler 순서는 다음과 같이 구할 수 있다.

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

재귀

방향그래프가 위 그림 처럼 주어졌을 때 각 노드에 순서를 위의 규칙과 같이 구할 수 있다. 이때 마지막 노드인 바다와 만나는 노드의 순서가 이 하천계 그래프의 Strahler의 순서가 되는데 이를 구하는 문제

 

접근방법

처음에 Strahler 순서가 무엇인지를 이해하는데 시간이 걸렸다. 결국 더이상 나가는 강이 없는 노드인 마지막 번째 노드의 순서를 구하는 문제였다.

우선 인접 리스트를 만드는데, 각 노드에서 뻗어나가는 노드를 갖는게 아니라 들어오는 노드를 갖도록 만들었다.

즉 위의 그래프로 인접 리스트를 만든다면 아래와 같이 만들어짐

1 | 
2 |
3 | 1, 2
4 | 6, 3
5 | 3
6 | 
7 | 6, 4, 5

 

이 상태에서 결국 구해야할 것은 마지막 7번 노드의 순서니까

7번 노드의 순서를 구하려면 6,4,5번의 순서를 구해야하고 그러려면 3번의 순서도 알아야하고, 그러러면 1,2번의 순서도 알아야 한다.

강의 근원지는 순서가 1이므로 거기까지 내려가면 재귀함수를 종료할 수 있도록 재귀함수를 만들었다.

재귀함수(getSeqOf)는 우선 매개변수로 구해야할 노드를 입력받고

- 그 노드의 순서를 이미 구했다면 순서를 바로 리턴하고

- 아직 못구했다면 순서를 구하는 로직을 수행하도록 한다.

순서를 구하는 로직은 우선 본인에게 들어오는 노드를 인접리스트에서 찾아와서

그 노드들의 순서를 모두 구한다. 이 과정에서 재귀함수가 호출된다.

순서를 모두 구했다면 문제의 규칙에 따라서 이들 중 가장 큰 순서의 갯수를 따져서 1개보다 크면 그 순서+1, 1개면 그 순서가 본인의 순서가 된다.

특히, 재귀함수 초입에서 순서가 이미 있을 경우와, 본인에게 들어오는 노드가 없는 경우, 즉 강의 근원인 경우 1을 리턴하도록 한다.

이때 계속해서 순서를 구하지 않아도 되도록 순서를 한번 구하면 seq라는 순서를 저장하는 배열에 저장한다.

 

마지막 노드로 들어오는 모든 노드들의 순서가 구해지면 마지막 노드의 순서도 구해지므로 끝

 

오답노트

swift에서 array의 method인 count(where:)로 매개변수로 bool타입을 리턴하는 클로저를 전달하면 해당 클로저가 true인 원소만 카운트해주는 함수를 제공하는데, 백준에서는 컴파일 에러가 떠서 filter로 순서 배열을 한번 거른 후 count를 해줬다.

 

소스코드

import Foundation

func solution() {
    
    // input
    let T:Int = Int(readLine()!)!
    for _ in 1...T {
        let KMP:[Int] = readLine()!.split(separator: " ").map { Int($0)! }
        let K = KMP[0]
        let M = KMP[1]
        let P = KMP[2]
        
        var adj:[[Int]] = [[Int]](repeating: [], count: M+1)
        var seq:[Int] = [Int](repeating: 0, count: M+1)
        
        for _ in 0..<P {
            let edge:[Int] = (readLine()?.split(separator: " ").map { Int($0)! })!
            adj[edge[1]] += [edge[0]]
        }
        
        // 재귀
        func getSeqOf(_ m:Int) -> Int {
            if seq[m] != 0 {
                return seq[m]
            }
            if adj[m].count == 0 {
                seq[m] = 1
                return 1
            }
            // 순서 구해야할 때
            let chdr_seq:[Int] = adj[m].map { getSeqOf($0) }
            let maxSeq:Int = chdr_seq.max()!
//            let cnt = chdr_seq.count { $0 == maxSeq }
            let cnt = chdr_seq.filter{ $0 == maxSeq }.count
            if cnt > 1 {
                seq[m] = maxSeq + 1
            } else {
                seq[m] = maxSeq
            }
            return seq[m]
        }
        print(K, getSeqOf(M))
        // case 하나 끝 //
    }
    
}

solution()

 

내 로직대로 한번에 통과되는거 넘 뿌듯 ;)