프로그래밍/Algorithm

백준 11725 트리의 부모 찾기 파이썬

모지사바하 2021. 3. 30. 11:04

www.acmicpc.net/problem/11725

 

11725번: 트리의 부모 찾기

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

www.acmicpc.net

import sys
from collections import deque

sys.setrecursionlimit(100001)

if __name__ == '__main__':
    n = int(sys.stdin.readline().rstrip())
    graph = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b = map(int, sys.stdin.readline().split())
        graph[a].append(b)
        graph[b].append(a)

    visited = [False] * (n + 1)

    dic = {}


    def dfs(v):
        visited[v] = True
        for i in graph[v]:
            if not visited[i]:
                dic[i] = v
                dfs(i)


    dfs(1)
    for i in range(2, n + 1):
        if i in dic:
            print(dic[i])
        else:
            break

 

음.. DFS/BFS를 풀다보니 내가 요런 타입에 익숙치 않은듯하다.

인접리스트라 해야하나..?

 

뭐 암튼..  이상하게 이런타입의 문제를 만나면 머리가 잘 안돌아가면서 경직된다.

이 문제도 너무 쉬운 문젠데 사고가 순간 정지됐다.

그냥 딕셔너리 하나만들고 각 노드를 방문하면서 방문한 노드를 부모로 방문한 노드에 존재하는 다른 노드 번호를 자식으로 저장한 후,

순차적으로 출력해주면 끝이다.