[BOJ][Python]11725번 풀이

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

11725번: 트리의 부모 찾기

from collections import deque
import sys
ssr = sys.stdin.readline
sys.setrecursionlimit(10**7)

def dfs(parent):
    if visited[parent] == 1:
        return
    visited[parent] = 1
    for i in adjacency_list[parent]:
        if visited[i] == 0:
            ans[i] = parent
            dfs(i)

def bfs():
    tmp = sorted(adjacency_list[1])
    q = deque([])
    for i in tmp:
        ans[i] = 1
        q.append(i)
        visited[i] = 1
    while q:
        tmp = q.popleft()
        for i in adjacency_list[tmp]:
            if visited[i] == 0:
                visited[i] = 1
                q.append(i)
                ans[i] = tmp

n = int(input())
adjacency_list = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int, ssr().split())
    adjacency_list[a].append(b)
    adjacency_list[b].append(a)
visited = [0 for _ in range(n+1)]
ans=[0 for _ in range(n+1)]
# dfs(1)
bfs()
for i in range(2,n+1):
    print(ans[i])

오랜만에 또 재밌는 문제였습니다. 저는 이때까지 그래프 탐색 문제를 풀 때 주어진 입력을 그대로 사용하거나, 인접 행렬을 만들어서 사용했었습니다. 인접 리스트가 있다는 것은 알았지만 딱히 해당 방법을 이용하려고 생각해본 적은 없었습니다. 그런데 이 문제의 경우는 인접 행렬이나, 입력을 그대로 이용하면 시간초과가 나는 구조를 가지고 있습니다. 간단하지만 왜 그런지와 인접 리스트로 푸는 방법은 무엇인지 이번 포스팅에서 알아봅시다.

 

문제 접근은 기본적인 그래프 탐색입니다(dfs/bfs 둘 중에 원하는 거 쓰시면 됩니다. 저는 이왕 하는거 둘 다 사용해봤어요). 다만 본격적인 탐색에 앞서서 잠깐 노드의 갯수 n을 알아봅시다. n의 범위는 2~10^5까지인데요. 이미 해당 내용을 알고 계시거나 눈치가 빠르신 분들은 일반적인 dfs나 bfs를 사용하기에 n의 범위가 크구나 라는 생각이 드셨을 것 같습니다. 실제로 인접 행렬을 이용한 방법의 그래프 탐색 알고리즘은 모든 노드를 방문한다는 가정하에 O(n^2)의 시간복잡도를 가집니다(1번 노드에서 n번 노드까지 간선의 유무를 파악하는 걸 총 n번 하니까). 평소에 제가 사용하던 입력을 그대로 간선의 정보로 받아서 사용하는 방법또한 O(n^2)의 시간복잡도를 가집니다(인접행렬로 만드는 과정이 없고, 순서가 뒤죽박죽일 뿐 인접행렬과 프로세스적으로 완전히 동일함) 그렇다면 해당 문제에서 O(n^2)의 시간복잡도를 갖는 알고리즘으로 풀이를 진행하면 어떻게 될까요? 연산횟수는 최대 (10^5)^2 = 10^10이 되겠죠. 예전에 1억번 정도가 1초라는 얘기를 드렸던 적이 있습니다. 뭐 안따져봐도 가볍게 넘어버리는 걸 볼 수 있네요. 그렇다면 n^2아래로 떨어트려야 되겠습니다. nlogn이나 n 정도의 알고리즘이 필요하겠죠. 여기서 인접 리스트가 등장합니다.

 

인접 리스트란 간선의 정보를 가지고 있는 리스트를 말합니다. 좀 더 풀어서 설명하자면 리스트 그 자체가 노드끼리의 연결관계를 나타내고 있다고 말할 수 있겠네요. 이게 무슨 말이냐, 문제에서 준 예시 1의 입력을 가지고 인접 리스트를 한 번 만들어보겠습니다.

 

7
1 6
6 3
3 5
4 1
2 4
4 7

 

인접 리스트 :

1 = [6,4]

2 = [4]

3 = [6,5]

4 = [1,2,7]

5 = [3]

6 = [1,3]

7 = [4]

 

인접 리스트는 위에서 리스트 자체가 노드끼리의 연결 관계를 나타내고 있다 라고 말씀을 드렸는데요. 즉, 노드간의 연결을 리스트의 이름과 리스트의 원소로 나타낸 것입니다(반드시 이름인 것은 아닙니다. 이름이 리스트라 그렇지 해시테이블로 구성한다면 key가 될 것이고, 저처럼 인덱스를 이름 대용으로 쓴다면 인덱스가 되겠죠). 위의 인접 리스트로 설명을 드리자면 리스트 1은 노드 1과 6, 1과 4 사이에 간선이 존재함을 의미합니다. 그 아래도 전부 2 4, 3 6, 3 5, 4 1,... 전부 다 이름 또는 key 노드와 원소 노드들 간에 연결이 있다는 의미를 지닙니다. 하지만 주의해야할 점은 항상 key 노드가 부모 노드인 것은 아니라는 것입니다. 예를 들면 1 = [6,4] 인데 4 = [1,2,7]로 1이 원소로 들어가있죠. 1은 root라서 무조건 부모 노드일 수 밖에 없는데 말이죠. 이처럼 이름이나 key가 무조건 부모 노드는 아니라는 사실을 기억해주시면 좋겠습니다.

 

인접 리스트가 무엇인지에 대해서는 알아봤습니다. 그렇다면 이제 인접 리스트를 왜 쓰는지를 한 번 알아봅시다. 인접 행렬이 시간 초과가 나는 이유가 무엇이었을까요? 알고리즘이 O(n^2)이라는 건 들어서 알겠는데 왜 n^2인걸까요? 인접 행렬을 처음부터 끝까지 탐색한다고 하면 n번 X n번 이니까 n^2이긴 한데 왜 처음부터 끝까지 탐색을 하는건가요? 그 이유는 모든 노드에 대해서 간선의 존재 여부를 파악하기 위해서입니다. 임의대로 탐색을 중간에 멈춰버리면 뒤에 있는 노드들은 확인을 못하니까 간선이 존재하는지도 모르고 제대로 탐색했다고 말할 수 없겠죠. 해당 문제처럼 모든 간선을 다 돌아봐야 하는 경우라면 모든 노드를 돌면서 간선의 존재 여부를 파악해야하니 자연스럽게 O(n^2)의 형태를 가짐을 알 수 있겠죠. 인접 리스트라면 어떨까요? 1번에서 시작한 다음 6번에서 탐색을 진행해야 한다고 할 때, 인접 행렬이었다면 6번과 1번, 6번과 2번,...6번과 7번까지 n번을 돌아야했겠죠. 그 중에는 6번과 간선을 안가진 노드도 있으니 불필요한 작업또한 존재할겁니다. 하지만 인접 리스트를 이용한다면 리스트 6에 있는 원소에 대해서만 탐색을 진행하면되니 간선이 존재하지 않는 노드를 신경쓸 필요가 없어서 불필요한 작업이 줄어들겠죠(당장 6번에 대해서만 비교해보면 7번은 돌아야했던 작업이 2번만 돌면 되는 작업으로 바뀝니다). 따라서 인접 리스트를 이용한 그래프 탐색 알고리즘은 O(n)이 됩니다(Big-O 기준).

 

인접 리스트가 무엇인지, 왜 인접 리스트를 써야하는지는 설명을 드렸으니 다시 문제에 대한 설명으로 넘어가보죠. 해당 문제는 각 노드의 부모 노드가 무엇인지를 출력하는 문제입니다. 저도 처음에는 이걸 어떻게 풀지 고민을 좀 했으나, 트리의 구조를 생각해보면 너무나도 간단한 문제입니다. 트리는 root로 부터 출발해서 모든 노드에 접근이 가능합니다. 그말은 root를 제외한 모든 노드는 부모가 존재하고 그래프 탐색을 진행하면 어떤 노드끼리 연결되어있는지를 알 수 있으니 순서대로 타고 가면 그 다음에 방문해야할 노드는 현재 노드의 자식 노드이고, 따라서 자식 노드의 부모 노드가 현재 노드라는 사실이 도출되는 것입니다. 따라서 해당 문제를 풀기 위해서 그래프 탐색 알고리즘을 사용하면 되겠죠(dfs/bfs).

 

사실 인접 리스트만 만들고 나면 나머지는 여러분이 항상 해오던 bfs나 dfs와 동일합니다. 1부터 시작해서 탐색을 진행하고 방문을 한다면 방문 처리를 하고, 이미 방문처리를 했다면 넘어가는 지극히 평범한 문제입니다. 따라서 열심히 그래프 탐색을 진행하고 출력을 하기 위한 작업을 좀 해주면 되겠습니다. 저는 ans라는 리스트를 만들어서 ans[i]는 'i노드의 부모노드' 가 되도록 값을 저장해줬습니다. 그리고 2번부터 줄을 바꿔가면서 출력해주면 되겠죠.

 

문제 자체는 사실 간단했는데 해당 문제를 풀기 위해서 안쓰던 걸 배워야 했다는 사실이 좀 즐거웠습니다. 그러다보니 또 말이 많아졌네요. 상당히 괜찮은 방법인 것 같아서 자주 이용할 것 같습니다. 다만 장점만 있다면 모든 dfs 문제를 풀이할 때 다들 인접 리스트를 이용할텐데 그러지 않는 걸 보면 장점만 있는 방법은 아닌 것 같은데요. 어떤 경우에는 쓰면 안되는지 궁금하네요. 혹시 아시는 분이 있으시다면 댓글로 남겨주시면 감사하겠습니다.