0527_ 백준 11725번 : 트리의 부모 찾기/ DFS / Python

[문제 풀이]

- DFS(깊이우선탐색)으로 주어진 트리에서 노드의 부모를 찾는 문제

- 루트 1부터 시작해서 순차적으로 모든 노드의 부모를 찾아나가는 로직

- 처음에는 1부터 시작해서 목표로 하는 노드까지 찾아 내려가 부모를 찾는 로직을 짰다가, 런타임 에러가 나서 해결하지 못하고 코드를 수정하였다 => 1부터 시작해 중복 없이 모든 노드의 부모를 리스트로 저장했고, 덕분에 방문했는지 확인하는 VISIT 리스트도 생략할 수 있었다.

[코드 구현]

import sys
input = sys.stdin.readline

def dfs(adj, start, parent):
    s = [start]
    while s:
        tmp = s.pop()
        for i in adj[tmp]:
            # 부모 리스트에 i의 부모로 tmp를 넣어주고
            parent[i].append(tmp)
            s.append(i)
            # i의 인접 리스트에는 tmp를 제거해주기(중복 없애기 위해)
            adj[i].remove(tmp)
    return parent

n = int(input())
adj = [[] for _ in range(n+1)]
parent = [[] for _ in range(n+1)]
# 인접리스트 만들기
for i in range(n-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

result = dfs(adj, 1, parent)

# 2번 노드부터 결과값만 출력
for i in range(2,n+1):
    print(result[i][0])

[문제 출처]

백준 11725번 트리의 부모 찾기 https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기