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

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

11725번: 트리의 부모 찾기

2023.04.14 - [코딩 테스트/개념] - Tree

# 2 ≤ N ≤ 100,000

from collections import deque
import sys

readline = sys.stdin.readline

N = int(readline())
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    v1, v2 = map(int, readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)

parents = [0 for _ in range(N + 1)]
queue = deque([1])
visited = [True] + [False for _ in range(N)]

while queue:
    vertex = queue.popleft()
    visited[vertex] = True
    
    for adj_vertex in tree[vertex]:
        if visited[adj_vertex]:
            continue

        queue.append(adj_vertex)
        parents[adj_vertex] = vertex

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

처음엔 트리 문제라 해서 어떤 트리일까 했지만, 실은 그래프 문제였다!

인접 리스트로 트리를 표현하고(양방향 그래프로), bfs로 트리를 탐색하면서 부모 노드를 찾는 방식으로 풀었다.

트리이므로, 루트 노드부터 탐색할 때 이미 방문한 노드는 방문하지 않도록 처리했다(자식 -> 부모로 이동하지 않도록).

dfs로 풀어도 상관 없다! queue만 stack으로 바꾸고, popleft를 pop 메서드로 바꾸면 된다.

# 2 ≤ N ≤ 100,000

from collections import deque
import sys

readline = sys.stdin.readline

N = int(readline())
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    v1, v2 = map(int, readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)

parents = [0 for _ in range(N + 1)]
stack = deque([1])
visited = [True] + [False for _ in range(N)]

while stack:
    vertex = stack.pop()
    visited[vertex] = True

    for adj_vertex in tree[vertex]:
        if visited[adj_vertex]:
            continue

        stack.append(adj_vertex)
        parents[adj_vertex] = vertex

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

재귀 함수로 풀면,

# 2 ≤ N ≤ 100,000

import sys

readline = sys.stdin.readline

N = int(readline())
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    v1, v2 = map(int, readline().split())
    tree[v1].append(v2)
    tree[v2].append(v1)

parents = [0 for _ in range(N + 1)]
visited = [True] + [False for _ in range(N)]


def dfs(vertex):
    visited[vertex] = True

    for adj_vertex in tree[vertex]:
        if visited[adj_vertex]:
            continue

        parents[adj_vertex] = vertex
        dfs(adj_vertex)


dfs(1)

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