[백준 24479 파이썬] 알고리즘 수업 - 깊이 우선 탐색 1 (실버 2, DFS)

알고리즘 유형 : DFS
풀이 참고 없이 스스로 풀었나요? : X

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

SOLVE 1

stack 풀이

import sys
input = sys.stdin.readline

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# 내림차순인 인접 그래프를 스택에 하나씩 넣어주면, 나중에 스택에서
# 꺼낼때는 이들을 오름차순으로 꺼내게 됨
for i in range(1, len(graph)):
    graph[i].sort(reverse=True)

def DFS(start):
    stack = [start]
    visited = [-1]*(N+1)
    result = [0]*(N+1) # result[idx]는 idx노드를 방문한 순서 값을 의미함
    cnt = 1 # 방문 순서 값
    
    while stack:
        cnt_node = stack.pop()
        # 사이클이 있는 그래프 같은 경우에,
        # 어떤 노드에 대해, 그 노드의 인접 노드 K를 스택에 넣어
        # 놓은 뒤에, DFS를 수행하다가 더 깊은 깊이의 어느 노드에서
        # 인접 노드로 K를 또 스택에 넣는 경우가 생김.
        # 이 때의 K가 먼저 스택에서 꺼내져 처리되므로,
        # 맨 첨 넣어줬던 K는 스택에서 꺼낸 뒤 따로 코드를
        # 수행해주지 않고 넘어감
        if visited[cnt_node] == 1:
            continue
        
        visited[cnt_node] = 1
        
        # 방문 순서 값 저장
        result[cnt_node] = cnt
        cnt += 1
        
        # 아직 방문 이력 없으면(=스택에서 뽑은 적 없으면)
        # 스택에 싹 다 집어 넣기
        for adj_node in graph[cnt_node]:
            if visited[adj_node] == -1:
                stack.append(adj_node)
    
    return result

result = DFS(R)
    
print(*result[1:], sep="\n")

SOLVE 2

재귀 풀이

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N, M, R = map(int, input().split())
graph = [[] for _ in range(N+1)]
path = []
result = [0]*(N+1)
visited = [-1]*(N+1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

for i in range(1, len(graph)):
    graph[i].sort()

def DFS(start):
    visited[start] = 1
    path.append(start)
    
    for adj_node in graph[start]:
        if visited[adj_node] == -1:
            DFS(adj_node)
    
    return

DFS(R)

for idx, node in zip(range(1, len(path)+1), path):
    result[node] = idx
    
print(*result[1:], sep="\n")

SOLVE 1) 풀이 요약 (stack 풀이)

1. 사이클이 존재하는 그래프의 경우의 stack DFS를 생각해봐야 하는 문제이다.

   stack 풀이에서는, cnt_node에 대해, 인접 노드를 모두 stack에 넣는다.

   여기서 visited를 언제 갱신해줄거냐가 핵심이다.

   만약 K를 stack에 넣을 때 visited를 갱신해줘버리면, cnt_node에서 DFS를 더 수행해서 더 깊은 depth의 어떤 노드에서 다시 K를 만날 수도 있다.(사이클이 있기 때문)

   좀 더 DFS를 수행한 후에, 어느 순간 K를 스택에서 뽑게 되면, 맨 첨에 cnt_node의 인접 노드라 스택에 넣었던 K는 쓸모가 없게 된다.

   그런데 cnt_node를 순회할 때 K를 넣으면서 visited를 갱신시켜버리면 더 깊은 depth의 K를 스택에 넣을 수 없으므로 에로사항이 생긴다.

   즉, 스택에서 직접 뽑아 K를 확실히 조회하는 경우에 visited를 갱신해주기 전까지는 K를 만날때마다 무조건 stack에 다 집어넣어준다.

   그리고 stack에서 K를 뽑았을 때 visited가 1이면 아무 동작도 수행을 안해주면 중복 처리를 피할 수 있다.

SOLVE 2 풀이 요약 (재귀 풀이)

1. stack 풀이에 비하면 간단하다.

   DFS를 호출함은 곧 그 노드를 조회했다는 것을 의미한다. 그러므로 호출됐을 때 visited를 갱신하고 path에 append해준다.

   이 때 visited는 DFS 호출 시에 갱신해줘도 되고, 인접 노드를 순회할 때 갱신해줘도 된다.

   인접 노드를 일단 stack에 싹 다 넣고보는stack 풀이와 달리,

   인접 노드들 중에 오름차순 기준 왼쪽 노드부터 DFS를 다 돌고, 그 다음 두 번째 노드를 DFS 돌고, 이런 식으로 진행하기 때문에 임의의 노드를 중복 처리하는 경우가 없다.

배운 점, 어려웠던 점

• DFS에 대한 이해도가 아직 부족하다는 점을 깨닫게 해준 문제였다. 내가 기존에 활용하던 DFS 풀이는 사이클이 존재하는 그래프에 대해 재귀 풀이는 가능하지만, stack 풀이로는 풀 수 없는 풀이였다.

  사이클이 존재하는 그래프를 stack을 활용하여 DFS하는 방법을 알게 되었다.