(Python/🥈2)백준 알고리즘 11725번 : 트리의 부모 찾기

백준알고리즘

 

문제:

 

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

문제:

 

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

문제:

 

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

 

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())
graph = [[] for i in range(N+1)]

def dfs(x):
    for i in graph[x]:
        if visited[i] == 0: # 미방문
            visited[i] = x
            dfs(i)

for i in range(N-1):
    x, y = map(int,sys.stdin.readline().split(" "))
    graph[x].append(y)
    graph[y].append(x)

visited = [0] * (N+1)
print(graph)
dfs(1)
for i in range(2,N+1):
    print(visited[i])

 

 

dfs를 사용했다. 

 

양방향 이니깐 graph에 추가해주고.

 

1부터 실행하면 되는데, 만약 graph[1] 을 하면 4와 6과 연결이 되어있다.

그러면 visited[4], visited[6] 을 1을 해주므로써 부모노드의 값을 저장한다.

그리고 또 다음 graph[4] 에 연결된 2, 7 을 호출하면서 visited 2, 7을 4로 저장해주는식이다.

 

 

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
sys.setrecursionlimit(10**6)

N = int(sys.stdin.readline())
graph = [[] for i in range(N+1)]

q = deque()
q.append(1)
def bfs():
    while q:
        node = q.popleft()
        for n_node in graph[node]:
            if visited[n_node] == 0:
                visited[n_node] = node
                q.append(n_node)
for i in range(N-1):
    x, y = map(int,sys.stdin.readline().split(" "))
    graph[x].append(y)
    graph[y].append(x)

visited = [0] * (N+1)
print(graph)
# dfs(1)
bfs()


for i in range(2,N+1):
    print(visited[i])

bfs를 사용하면 이렇게 할 수 있다.