[BOJ 11725] 트리의 부모 찾기 (C++)

 

Problem

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

11725번: 트리의 부모 찾기

 

Comment

첫 번째 줄에 노드의 개수(N)를 받습니다. 두 번째 줄 부터 N-1개의 트리 상에서 연결된 두 정점을 받습니다(예를 들어, 노드를 7개 받았다면 6개의 연결된 두 정점을 받습니다.).

 

연결된 두 정점을 vector에 받으면서 추가해줍니다(이 때, 두 정점 각각 저장합니다.). 예를 들어, 두 정점 (1, 6)을 받았다면 tree[1].push_back(6)과 tree[6].push_back(1)을 수행하면서 tree[1]과 tree[6] 각각에 정점을 추가하는 것입니다.

 

두 정점 각각 저장하는 이유는, 앞으로 탐색하면서 서로 연결되어 있는지 알기 위해서입니다. 문제의 '예제 입력 1'을 보겠습니다.

6줄의 정점 노드들을 tree vector에 다 추가했다 치고, 1번부터 탐색을 시작합니다. 우리는 DFS를 쓸 것이므로, 끝의 원소가 나올 때 까지 계속 찾습니다. 1번이 루트 노드라고 문제에 정의되어 있으므로, tree[1]부터 시작합니다(findParent(1)이 실행되면서 시작됩니다.).

 

<findParent(1)>

tree[1]의 첫 번째 원소는 6입니다(1 -> 6). tree[1]에 방문했으므로 visited[1]을 true로 변경해줍니다(현재 tree[1]에는 6, 4가 차례대로 붙어있습니다.). tree[6]을 방문하지 않았으므로 6번 노드의 부모를 1번 노드로 설정(parent[6] = 1)하고 6번 노드(tree[6])를 방문합니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: undefined
- 3번 노드의 부모: undefined
- 4번 노드의 부모: undefined
- 5번 노드의 부모: undefined
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

<findParent(6)>

tree[6]을 방문했으므로 visited[6]을 true로 변경해줍니다(visited[6] = true). 현재 6번 노드에는 1, 3이 차례대로 붙어있습니다. 하지만, 1번 노드는 제일 먼저 방문했으니(visited[1] == true) 갈 수 없고 3번 노드의 부모를 6번 노드로 설정(parent[3] = 6)하고 3번 노드(tree[3])를 방문합니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: undefined
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: undefined
- 5번 노드의 부모: undefined
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

 

<findParent(3)>

tree[3]을 방문했으므로 visited[3]을 true로 변경해줍니다(visited[3] = true). 현재 3번 노드에는 6, 5가 차례대로 붙어있습니다. 6번 노드는 방문했으므로(visited[6] == true) 5번 노드의 부모를 3번 노드로 설정(parent[5] = 3)하고 5번 노드(tree[5])를 방문합니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: undefined
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: undefined
- 5번 노드의 부모: 3번 노드 (tree[3])
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

<findParent(5)>

tree[5]를 방문했으므로 visited[5]를 true로 변경해줍니다(visited[5] = true). 현재 5번 노드에는 3번 노드가 붙어있습니다. 하지만, 3번 노드는 이미 방문했으므로(visited[3] == true) 더 이상 방문할 곳이 없으므로 1번 노드로 돌아갑니다(3번 노드, 6번 노드로 돌아가도 더 이상 탐색할 곳이 없기 때문에 결과적으로 1번 노드로 돌아갑니다.).

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: undefined
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: undefined
- 5번 노드의 부모: 3번 노드 (tree[3])
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

다시 findParent(1)로 돌아갑니다.

<findParent(1)>

tree[4]를 방문하지 않았으므로 4번 노드의 부모를 1번 노드로 설정(parent[4] = 1)하고 4번 노드(tree[4])를 방문합니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: undefined
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: 1번 노드 (tree[1])
- 5번 노드의 부모: 3번 노드 (tree[3])
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

<findParent(4)>

tree[4]를 방문했으므로 visited[4]를 true로 변경해줍니다(visited[4] = true). 현재 4번 노드에는 1, 2, 7이 차례대로 붙어있습니다. 하지만, 1번 노드는 제일 먼저 방문했으니(visited[1] == true) 갈 수 없고 2번 노드와 7번 노드를 차례대로 방문하면 될 것 같습니다. 일단 2번 노드 먼저 방문합니다. 2번 노드의 부모를 4번 노드로 설정하고(parent[2] = 4) 방문하겠습니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: 4번 노드 (tree[4])
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: 1번 노드 (tree[1])
- 5번 노드의 부모: 3번 노드 (tree[3])
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

<findParent(2)>

tree[2]를 방문했으므로 visited[2]를 true로 변경해줍니다(visited[2] = true). 현재 2번 노드에는 4가 붙어있습니다. 4번 노드는 이미 방문했으므로(visited[4] == true) 다시 4번 노드로 되돌아가서 마저 찾습니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: 4번 노드 (tree[4])
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: 1번 노드 (tree[1])
- 5번 노드의 부모: 3번 노드 (tree[3])
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: undefined

 

<findParent(4)>

아까 찾다가 말았던 7번 노드로 찾겠습니다. 7번 노드의 부모를 4번 노드로 설정하고(parent[7] = 4) 방문하겠습니다.

현재 상황
- 1번 노드의 부모: X (root node)
- 2번 노드의 부모: 4번 노드 (tree[4])
- 3번 노드의 부모: 6번 노드 (tree[6])
- 4번 노드의 부모: 1번 노드 (tree[1])
- 5번 노드의 부모: 3번 노드 (tree[3])
- 6번 노드의 부모: 1번 노드 (tree[1])
- 7번 노드의 부모: 4번 노드 (tree[4])

 

<findParent(7)>

tree[7]을 방문했으므로 visited[7]을 true로 변경해줍니다(visited[7] = true). 현재 7번 노드에는 5가 붙어있습니다. 하지만 이미 방문했으므로(visited[5] == true) 돌아갑니다. 이제 모든 노드를 찾았습니다.

 

findParent(1)가 최종적으로 종료되면 parent[2]부터 parent[N-1]까지 차례대로 출력합니다.

 

Code

 

Result

 

Remark

보통은 트리를 짤 때 루트를 정하면서 시작합니다. 하지만 이 문제는 트리의 루트를 나중에 정한다는 점이 일반적인 경우와 다른 점입니다. 따라서 문제를 풀 때 트리의 루트를 1로 정하는 것에 주의합니다.