[Python] 백준, 11725(트리)

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

11725번: 트리의 부모 찾기

본격적으로, BFS - DFS 문제들이 등장한다. 어떤 식으로 작동하는지는 책을 통해 공부한 바가 있지만, 실질적으로 구현해보지는 않아서 구글링을 통해 몇 번 연습한 뒤 문제 풀이에 임했다. 

 

우선 느낀 점은 단순히 알고리즘을 구현하는 일과 그걸 직접 문제에 적용시키는 일은 정말 다르다는 점이다. 거의 3시간을 BFS, DFS에 쏟을 정도로 오래 걸리더라. 남의 코드를 직관적으로 이해하는 능력이 조금 부족해서 공부의 효율이 떨어지는 듯한다.

 

내가 구현해 본 BFS, DFS를 먼저 소개한 뒤 11725번 풀이로 넘어가는 게 좋을 것 같다.

 

 

# PYTHON CODE (1) - BFS(넓이 우선 순회)

from collections import deque

def bfs1(graph, node):
    queue = deque([node])
    visited = []

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n]

    return visited

우선 시간 단축을 위하여 deque모듈을 가져왔다. 넓이 우선 순회는 큐를 이용해야 하는데, 먼저 들어온(같은 레벨의) 자료들을 처리해줘야 하므로 스택보다는 큐가 적합하다. 

 

 

 

# PYTHON CODE (2) - DFS(깊이 우선 순회)

def dfs1(graph, node):
    visited = []
    stack = [node]

    while stack:
        n = stack.pop()
        if n not in set(visited):
            visited.append(n)
            stack += set(graph[n]) - set(visited)

    return visited


def dfs2(graph, node, visited):
    visited.append(node)

    print(node, end=' ')
    print(visited)

    for i in graph[node]:
        if i not in visited:
            dfs2(graph, i, visited)

깊이 우선 순회는 재귀와 비재귀를 이용하여 두 가지로 구현할 수 있다. 위에 언급한 것과 반대로 가장 최근에 들어온 자료를 끝까지 탐색해야 하기에 스택이 적합하다.

 

 

# PYTHON CODE(3) - 11725번

import sys

n = int(sys.stdin.readline())

tree = [[] for _ in range(n + 1)]
visit = [0] * (n + 1)
visit[1] = 1

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


def dfs(node):
    stack = [node]

    while stack:
        parent = stack.pop()
        for child in tree[parent]:
            if not visit[child]:
                visit[child] = parent
                stack.append(child)
    print('\n'.join(map(str,visit[2:])))


dfs(1)

구현은 DFS나 BFS 중 어느 것으로 하던 상관이 없다. 

 

- for문은 input에서 연관된 자료들을 정리해주는 반복문이다. 인덱스에 착오가 없도록 사전에 n + 1의 []를 생성해주었다. 즉, 인덱스 자체가 노드의 key값이 되어준다.

- visit은 부모 노드들을 정리해놓은 리스트인데, 루트 노드가 1임을 문제에서 제시해주었으므로 visit[1] = [1]을 지정해두었다. 

- dfs함수는 부모 노드인 1부터 시작하며 1의 자식 노드들부터 탐색하며 반복문을 돈다. visit 리스트는 visit[1]을 제외하고는 사전에 0을 지정해두었으므로, 순차적으로 값을 입력받아 꼬임이 없도록 if문에서 처리된다. 

 

 

 

꽤 까다로운 알고리즘이라고 알고 있었는데, 이제야 본격적으로 뭔가가 시작된 기분이다.