트리의 부모 찾기

❓문제

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

❗문제 정리

dfs /bfs를 사용하여 문제 풀기!

📑코드

1. DFS

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

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

result=[[] for _ in range(n+1)]
def dfs(graph, v, visited):
    global result
    visited[v]=True
    #print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            result[i].append(v)
            dfs(graph, i, visited)

visited=[False]*(n+1)
dfs(graph, 1, visited)

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

2. BFS

from collections import deque
import sys
input=sys.stdin.readline

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

result=[[] for _ in range(n+1)]

def bfs(graph, start, visited):
    queue=deque([start])
    visited[start]=True
  
    while queue:
        v=queue.popleft()
    
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                result[i].append(v)
                visited[i]=True

visited=[False]*(n+1)
bfs(graph, 1, visited)

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

📝코드 설명

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

노드의 개수 n을 입력받고, 양방향 그래프를 그린다.
예제1의 graph 모습

result=[[] for _ in range(n+1)]
def dfs(graph, v, visited):
    global result
    visited[v]=True
    #print(v,end=' ')
    for i in graph[v]:
        if not visited[i]:
            result[i].append(v)
            dfs(graph, i, visited)

visited=[False]*(n+1)
dfs(graph, 1, visited)

• dfs에서 v노드와 연결된 다른 노드 i가 한번도 방문하지 않았을 경우, i에서 다시 dfs를 시작한다. 이 말은, v가 i랑 연결되어있고, v는 i의 루트 노드라는 것이다.
• 출력형식이 노드 2~n 순서의 루트 노드를 출력하는 것이므로, 자식노드 i 인덱스에 루트 노드 v를 넣는다. (result)

result=[[] for _ in range(n+1)]

def bfs(graph, start, visited):
    queue=deque([start])
    visited[start]=True
  
    while queue:
        v=queue.popleft()
    
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                result[i].append(v)
                visited[i]=True

-bfs에서도 동일하다. v와 연결된 노드 i가 방문처리 되어있지 않는다면, 큐에 i를 넣고 루트노드를 출력하기 위한 result리스트에 자식노드 i인덱스에 루트 노드 v를 넣는다.

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

• 이후 result의 값을 출력한다. 지정 index에 값을 넣어주기 위한 이중 리스트이기 때문에 asterisk(*)를 사용하여 출력해준다.
• 부모 노드 번호를 2번 노드부터 순서대로 출력하라는 문제 지시로 2부터 for문 시작.

예시1번의 result

2번 노드의 부모노드 4
3번 노드의 부모노드 6
4번 노드의 부모노드 1
5번 노드의 부모노드 3
6번 노드의 부모노드 1
7번 노드의 부모노드 4

🎖제출 결과

1. DFS 제출결과
   
2. BFS 제출결과
   

💡insight