[CodingTest] 백준 #11725 트리의 부모 찾기

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

11725번: 트리의 부모 찾기

 

이 문제는 트리의 부모를 찾는 문제이다. 

예전에 C로 트리 문제를 풀었을 때 재귀로 접근했던 미세한 ㅋㅋ 기억이 남아있어 재귀로 시도를 해보려고 했는데 ㅠ 결두번째 테스트케이스에서 무한루프에 빠지면서 결국 성공하지 못했다 ㅠㅠ 

아직 BFS와 DFS를 제대로 공부하지 않아서 개념은 알지만 알고리즘을 짜는 것이 조금 힘들었다 ㅠ 인터넷을 참고했는데BFS 방법이라고 한다. BFS는 너비 우선 탐색으로 가까운 노드부터 방문한다. 

아래의 코드는 형제 노드들을 모두 모아놓고 순서대로 탐색한다.

 

BFS 코드

import sys
n = int(sys.stdin.readline())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    #연결된 노드들을 모두 tree에 넣기(인덱스를 부모로 하는 자식 노드들이 한 배열안에 들어있음)
    tree[a].append(b)
    tree[b].append(a)
#print(tree)
res = {}
p = [1]
#방문 여부 체크
checked = [False]*(n+1)
#print(checked)
while p:
    parent = p.pop(0)
    checked[parent] = True
    #parent의 자식 노드들을 살펴보자
    for item in tree[parent]:
    #아직 방문하지 않았다면 
        if not checked[item]:
        #방문처리
            checked[item] = True
            #결과 딕셔너리의 부모 세팅
            res[item] = parent
            #p에 item 넣기
            p.append(item)
        #    print(res)

for i in range(2,n+1):
    print(res[i])

 

 

 

DFS 코드

import sys
sys.setrecursionlimit(10**9) #런타임 에러 방지

def dfs(curr,tree,parents):
    for item in tree[curr]:
        if parents[item] == 0:
            parents[item] = curr
            #자식 노드에 대해 계속 탐색해 나간다.
            dfs(item,tree,parents)
    
    

n = int(sys.stdin.readline())
tree = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    tree[a].append(b)
    tree[b].append(a)

res = {i:0 for i in range(1,n+1)}
#print(res)

dfs(1,tree,res)
for i in range(2,n+1):
    print(res[i])

 

런타임에러가 나면 recursionlimit을 설정해주면 된다고 한다. 처음에 작은 수를 넣었다가 다시 런타임 에러가 나서 큰 수로 바꿔주었더니 성공했다.

---

코드 참조 : https://keoroo.tistory.com/80 

출처: https://fullmoon1344.tistory.com/113