11725번: 트리의 부모 찾기

 

11725번: 트리의 부모 찾기

 

트리의 부모 찾기 

 

문제

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

예제 입력 1 

7
1 6
6 3
3 5
4 1
2 4
4 7

예제 출력 1 

4
6
1
3
1
4

---

풀이

문제는 쉽다. 

 

• 트리의 루트를 1이라고 주어질 때, 각 노드의 부모 노드를 구하면 된다.

 

그래프 문제는 자바로 몇번 풀어봤어서 알고리즘을 떠올리는데 어려움이 없었다.

각 노드들을 연결리스트로 만들어주고 dfs를 사용했다.

 

---

설계

 

1️⃣ 연결리스트 어떻게?

 

예제 1을 예시로 생각해보자.

각 노드 1~7까지의 리스트에 연결된 각 노드들을 붙여준다.

그러면 아래의 그림처럼 연결된 모습을 확인할 수 있다.

 

 

2️⃣ 부모 노드 탐색

 

dfs로 root 노드인 1번 노드부터 탐색을 하고, 해당 노드를 방문하지 않았다면 부모 노드를 탐색하도록 dfs를 만든다.

출력은 1번노드를 제외한 2번노드부터 차례대로 부모노드를 출력한다.

 

---

구현

1️⃣ 연결리스트 어떻게?

 

 

2️⃣ 부모노드 탐색 어떻게?

 

• result가 0이라면 => 방문하지 않은 노드라면 
• node는 부모노드, i는 자식노드를 의미

 

 

---

전체코드

 

let N = Int(readLine()!)!
var arr = [[Int]](repeating: [Int](repeating: 0, count: 0), count: N + 1)

var result = [Int](repeating: 0, count: N+1)

for _ in 0..<N-1{
    let input = readLine()!.split(separator: " ").map{Int($0)!}
    let a = input[0], b = input[1]
    arr[a].append(b)
    arr[b].append(a)
}
dfs(1)

func dfs(_ node: Int){
    for i in arr[node]{
        if result[i] == 0{
            result[i] = node
            dfs(i)
        }
    }
}
for i in 2..<N+1{
    print(result[i])
}