TIL) DFS 개념 이해하기

이 글은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

🎢 DFS는 노드 끝까지 갔다가 돌아온다

백준 11725 트리의 부모 찾기 : https://www.acmicpc.net/problem/11725

• 소스코드

N = int(input())

graph = { i : [] for i in range(1, N+1)}

for _ in range(N-1):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

parent = [0]*(N+1)
stack = []


def dfs(i):
    global parent, stack
    stack.append(i)
    for j in graph[i]:
        if j not in stack:
            print('dfs 이전:', stack)
            dfs(j)
            print('                     dfs 이후:', stack)
            parent[stack[-1]] = stack[-2]
            stack.pop()

dfs(1)

print(stack)
print(parent)

• 출력
  

💡 아이디어
연결되어있는 노드의 끝까지 갔다가 (1->6->3->5) 함수를 빠져나오면서 부모 노드를 찾을 수 있다.
stack[-1]의 부모는 stack[-2]에 저장되어있다.
stack[-1]의 부모를 저장해놓고 stack.pop()으로 제일 끝 노드를 없애버린다.

🧐 시간초과 해결

if j not in stack:

not in 으로 스택에 값이 있는지 확인하면 시간 복잡도가 O(n)이라서 시간이 꽤 많이 걸린다.
이를 해결하기 위해서는

visited = [False]*(N+1)
'''
중략
'''
if not visited[j]:

이런식으로 boolean으로 해당 노드를 방문했는지 저장해놓으면 O(1)으로 시간을 줄일 수 있다.