[백준/BOJ] 11725번 트리의 부모 찾기 (Swift, 스위프트)

문제 난이도: 실버 2

 

사용 알고리즘: DFS

import Foundation

let vertexCount = Int(readLine()!)!

var injacent: [[Int]] = Array(repeating: [], count: vertexCount + 1)
var parent: [Int] = Array(repeating: 0, count: vertexCount + 1)
var visited: [Bool] = Array(repeating: false, count: vertexCount + 1)


for _ in 0 ..< vertexCount - 1 {
    
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    
    injacent[input[0]].append(input[1])
    injacent[input[1]].append(input[0])
}

func dfs(start: Int) {
    
    visited[start] = true
    for injac in injacent[start] {
        if !visited[injac] {
            parent[injac] = start
            dfs(start: injac)
        }
    }
}

dfs(start: 1)

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

 

인접 리스트로 우선 각각 연결된 노드들을 저장했다.

 

[[], [6, 4], [4], [6, 5], [1, 2, 7], [3], [1, 3], [4]]

 

1 - 6,4

2 - 4

3 - 6,5

4- 1,2,7

5 - 3

6 - 1, 3

7 - 4

 

입력 1의 경우 위와 같이 연결된다.

루트가 1부터 트리로 존재하기 때문에 모두 기본적으로 연결되어 있다.

 

1부터 DFS로 탐색을 시작하는데, 이때 인접리스트의 인덱스 번호가 부모가 되고, 그 안에 존재하는 노드들이 자식이 된다.

 

방문한 노드를 제외하게 되면, 자식과 부모가 일치할 일은 제외된다.