[BOJ] 11725번 : 트리의 부모 찾기

🔒 문제

⌨ 입력

🖨 출력

📚 예제

 

 

📌 풀이

문제를 너무 어렵게 생각했던 것 같다.

그냥 진짜 그래프 문제였다.

신기하게 풀어본다고 이것저것 시도하다 그냥 DFS로 풀었다.

문제에서 주어지는 간선들을 graph에 저장하고, DFS로 1부터 시작해서 재귀함수를 써가며 풀었다.

parents = [0, 0, 0, 0, 0, 0, 0, 0]

graph에 저장된 것들을 적어본다면

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

이다.

dfs(1)을 해주면

1. graph[1]에서 첫번째 값인 6의 parents가 0인지 확인하고, parents[6]을 1로 바꿔준다.

parents = [0, 0, 0, 0, 0, 0, 1, 0]

dfs(6)을 해준다

2. graph[6]에서 첫번째 값인 1의 parents가 0인지 확인하고, parents[0]을 6으로 바꿔준다.

parents = [0, 6, 0, 0, 0, 0, 1, 0]

dfs(1)을 해준다.

3. graph[1]에서 첫번째 값인 6의 parents[6] = 1 이기 때문에 그 다음 값인 4를 확인하고, parents[4]를 1로 바꿔준다.

parents = [0, 6, 0, 0, 1, 0, 1, 0]

dfs(4)을 해준다.

4. graph[4]에서 첫번째 값인 1의 parents[1] = 6 이기 때문에 그 다음 값인 2를 확인하고, parents[2]를 4로 바꿔준다.

parents = [0, 6, 4, 0, 1, 0, 1, 0]

dfs(2)을 해준다.

5. graph[2]에서 첫번째 값인 4의 parents[4] = 1 이고 더이상 다른 값이 없기 때문에, dfs(2)를 끝내고 dfs(4)를 이어서 진행한다.
6. dfs(4)에서 1, 2 다음은 7이다. parents[7] = 4로 바꿔준다.

parents = [0, 6, 4, 0, 1, 0, 1, 4]

dfs(7)을 해준다.

7. graph[7]에서 첫번째 값인 4의 parents[4] = 1 이고 더이상 다른 값이 없기 때문에, dfs(7)을 끝내고 dfs(4)를 이어서 진행한다.
   하지만 dfs(4)도 끝났기 때문에 dfs(1)로 넘어간다.
   dfs(1)도 4가 마지막이기 때문에 dfs(6)으로 넘어가고, dfs(6)에서는 1다음인 3의 parents를 확인하고 6을 넣는다.

parents = [0, 6, 4, 6, 1, 0, 1, 4]

dfs(3)을 해준다.

8. graph[3]에서 첫번째 값인 6의 parents[6] = 1 이라 다음 값인 5로 넘어가서 parents[5]를 3으로 바꿔준다.

parents = [0, 6, 4, 6, 1, 3, 1, 4]

dfs(5)을 해준다.

9. graph[5]엔 3밖에 없고, parents[3] = 6이기 때문에 dfs(5)를 끝내고, dfs(3), dfs(6), dfs(1)까지 거슬러 올라가서 방문을 멈춘다.

이제 parents에 저장된 값들을 출력만 해주면 된다.

재귀 함수 호출하는 과정을 살펴 보면

dfs(1) -> dfs(6) -> dfs(1) -> dfs(4) -> dfs(2) -> dfs(7) -> dfs(3) -> dfs(5) 순이다.

나중에 이해하기 쉽게 그림을 그려서 다시 업데이트 해 보겠다.

다음에 시간이 된다면 BFS로도 풀어봐야겠다.

🔑 python 코드

#트리의 부모 찾기
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N = int(input())
graph = [[] for _ in range(N + 1)]
parents = [0 for i in range(N + 1)]

for _ in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    for i in graph[v]:
        if not parents[i]:
            parents[i] = v
            dfs(i)

dfs(1)

for i in range(2, N + 1):
    print(parents[i])