[Baekjoon][Python] 11725번 트리의 부모 찾기

11725번 트리의 부모 찾기

문제

풀이

트리에서 각 노드의 부모를 구하면 되는 것이다.

풀이는 매우 간단하다. DFS 탐색을 하면서 사용했던 visited 대신 해당 배열(parentArr)에 부모의 번호만 넣어주면 된다.

코드는 다음과 같다.

import sys
sys.setrecursionlimit(10**6)
class Graph:
    def __init__(self):
        self.graph = {}
    def addVertex(self, vertex):
        self.graph[vertex] = []
    def addEdge(self, startVertex, endVertex):
        self.graph[startVertex].append(endVertex)


def searchParent(graph, startVertex, parentArr):
    for s in graph.graph[startVertex]:
        if parentArr[s] == 0:
            parentArr[s] = startVertex
            parentArr= searchParent(graph, s, parentArr)
    return parentArr
            
# 노드의 개수
N = int(sys.stdin.readline())

# 그래프 선언
cGrpah = Graph()
parent = []

# vertex 추가
for i in range(N):
    cGrpah.addVertex(i + 1)
    parent.append(0)
parent.append(0)

# edge 추가
for i in range(N - 1):
    c1, c2 = map(int, sys.stdin.readline().split())
    cGrpah.addEdge(c1, c2)
    cGrpah.addEdge(c2, c1)

searchParent(cGrpah, 1, parent)
for data in parent[2:]:
    print(data)

결론

여러 문제를 통해 DFS, BFS에 익숙해지는 것이 가장 최선인 것 같다.