Tree 구조 문제 접근방식 정리

이글은 Tree구조의 알고리즘 문제를 풀고자할때, 제가 취했던 접근방식들을 정리하고자 작성한 글입니다. 미숙한 점이 아직 많지만, 정리가 되는대로 업데이트를 진행하고자 합니다.

 

알고리즘을 풀기 이전 가장 먼저 정해야할 것은 탐색 방식을 결정하는 것입니다.

• DFS: 경로찾기, 사이클 탐지와 같이 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 방식의 경우 사용
• BFS: 최단 경로 문제나 레벨 단위 처리와 같이 같은 레벨의 노드들을 먼저 탐색하는 방식의 경우 사용

탐색방식이 결정되었다면, 어떤 패턴을 사용할 수 있는지 확인합니다.

Bottom-up 접근

• 최하단 노드부터 루트로 올라가는 방식:
• 트리의 높이 구하기, 트리의 지름구하기와 같은 케이스에 유용

Top-down 접근

• 경로의 합구하기, 레벨 순회와 같이 루트에서 시작해서 아래로 내려가는 방식

 

이후 마지막으로 DFS건 BFS건 순회 혹은 재귀를 종료시키는 조건을 정의하였습니다. 이는 문제가 요구하는 내용에 따라 다르겠지만, 빈 노드를 만나거나, 최하단 노드를 만났을때와 같은 경우를 생각해볼 수 있습니다.

트리의 부모 찾기

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

let N = Int(readLine()!)!
var graph = [Int:Set<Int>]()
var parent = [Int:Int]()

for id in 1...N {
    graph[id]=Set<Int>()
}

for _ in 0..<N-1 {
    let arr = readLine()!.split(separator:" ").map{Int($0)!}
    graph[arr[0]]?.insert(arr[1])
    graph[arr[1]]?.insert(arr[0])
}

func findParent(current: Int, prev: Int) {
    parent[current] = prev
    
    for next in graph[current] ?? [] {
        if next != prev {
            findParent(current: next, prev: current)
        }
    }
}

findParent(current: 1, prev: 0)

for i in 2...N {
    print(parent[i]!)
}

가장 먼저, 데이터 구조를 설정하였습니다. graph를 Dictionary와 Set로 구현하게 된 이유는 우선 노드 간 간선이 양방향이여야 하기 때문입니다. 또한 한 노드가 2개 이상의 노드와 연결될 수도 있는 트리였기 때문에, 중복된 노드가 value에 추가되지 않도록 Set를 사용하였습니다.

그 이후, 반복문을 활용해 빈 세트를 삽입해 그래프를 초기화해주었습니다. 현재 그래프는 모두 value가 nil인 상태이기 때문에, 간선을 추가하기 위해 nil상태를 사전에 없애줘야 합니다. 

이후에, 간선 정보를 그래프 자료에 입력해주었습니다. 이때, 양방향 간선임을 고려하여 양쪽 모두에 간선 정보를 추가해주었습니다. 그리고, 간선의 개수는 노드-1이기 때문에 반복 횟수도 N-1로 하였습니다.

 

해당 알고리즘 문제의 경우, 노드의 부모 노드를 파악하는 것이 주 해결과제였습니다. 즉 양방향임에도, 두 노드가 있을때 어느 노드가 더 루트노드에 가까운지를 파악해야했죠. 이는 노드에 대한 탐색이 필요한 것이기에 DFS를 활용하였으며, 재귀함수를 설계함에 있어서 재귀호출하는 시점을 루트노드에서부터 파악하는 것이 용도에 더 적합하다고 생각하여, Top-down 접근방식을 생각하였습니다. 또한, 이전 노드에 대한 재귀호출을 방지하고자, prev 변수를 재귀함수의 인자로 전달하여 방문체크를 병행하였습니다. 

 

마지막으로, findParent 재귀함수로 설정한 parent 배열을 그대로 출력해주었습니다.

가장 먼 노드

https://school.programmers.co.kr/learn/courses/30/lessons/49189

func solution(_ n:Int, _ edge:[[Int]]) -> Int {
    // 양방향 그래프를 구성, 이때 중복되는 상황 방지하기 위해 Set 사용
    var graph = [Int:Set<Int>]()
    var visited = Set<Int>() // 방문한 노드 기록
    for i in 1...n {
        graph[i] = Set<Int>()  // 빈 Set으로 초기화
    }
    // 각 노드별로, 상대 노드 위치 삽입 -> 이때 Set로 값 타입 정하였으므로, 중복이 제거됨
    for e in edge {
        graph[e[0]]?.insert(e[1])
        graph[e[1]]?.insert(e[0])
    }
    var queue = [1] // 순회 대상 배열
    var lastLevelSize = 0 // 반환값 개수 저장용
    visited.insert(1)
    
    while !queue.isEmpty { // 방문해야하는 노드가 없을때까지 반복
        lastLevelSize = queue.count
        for _ in 0..<queue.count { // Queue를 모두 순회하며, LIFO 방식으로 각 노드마다 목적지 노드를 데려오고 나감.
            var current = queue.removeFirst()
            for neighbor in graph[current]! {
                if !visited.contains(neighbor){ // 이미 방문한 노드가 아닐 경우
                    visited.insert(neighbor) // 방문처리
                    queue.append(neighbor) // 이웃 추가
                }
            }
        }
    }
    return lastLevelSize
}

마찬가지로 양방향 간선으로 노드들이 연결되어있어서, Set와 Dictionary로 graph자료구조를 구성해준 후, 간선 정보들을 삽입하였습니다.

해당 문제는 레벨 단위로 탐색이 필요하며, 최단 거리를 계산하는 것이 필요하기 때문에 BFS라는 접근 방식을 선택하였습니다.

그리고 핵심 문제인 최종단계의 노드들 배열을 추출하고자 큐 자료구조를 활용하였는데요. 매 단계마다 큐에 있는 요소들을 순회하면서, 각 요소와 이웃된 노드들 중 지난 적이 없는 노드들을 추가해줍니다.

각 노드들의 방문 여부를 기록하기 위해 추가한 visited는 배열보다 contains 연산이 더 빠른 set로 구성하였는데, 이 변수를 통해 다음 queue 순회를 위한 노드들의 추가 기준에 활용합니다.

 

이러한 queue 순회를 반복되는 조건은 queue가 비어있을 때, 즉 더이상 큐에 저장되어있는 노드들이 방문할 수 있는 이웃노드가 하나도 없을때가 됩니다. 이웃노드가 없어 큐가 비게 되는 시점이 바로 노드에서 가장 먼노드가 큐에 있다는 것을 의미하게 됨으로, lastLevelSize를 순회 시작전마다 기록하여 줍니다.

 

감사합니다.