[그래프 탐색] 깊이 우선 탐색을 스택으로 구현하는 세 가지 방법 | 백준 2606번 파이썬

2606번: 바이러스

기본적인 깊이 우선 탐색 문제이다. 

 

stack을 이용하여 DFS를 구현했는데, 내가 구현한 방법이랑 일반적인 방법이랑 동작 방식이 조금 달라서 비교해보고자 글을 작성하게 되었다!

 

방법 1. 인접한 노드 하나만 추가 

[그래프 탐색] 깊이 우선 탐색 알고리즘이란 (DFS, Depth First Search) | 백준 1260번

 

 

위 글에서 유튜브 영상을 보고 작성한 부분을 참고하여 코드를 짰다. 

import sys
input = sys.stdin.readline

N = int(input()) # 컴퓨터 개수
M = int(input()) # 그래프 정보 개수 

graph = [[] for i in range(N+1)]

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

visit = [False] * (N+1) # 노드들의 방문여부가 T/F로 저장  
stack = []
v = 1
# DFS with stack
stack.append(v)
visit[v] = True
while stack:
    v = stack[-1] # 현재 방문한 노드
    for i in graph[v]: # 인접한 노드들 조사
        if visit[i] == False: # 방문한 적 없으면
            stack.append(i) # stack에 추가
            visit[i] = True # 방문 처리 
            break
    else: # 인접한 노드들이 모두 방문되었다면
        stack.pop() # 현재 노드 탐색 끝

num = 0
for i in visit:
    if i == True:
        num += 1
print(num-1) # 1번 컴퓨터 제외

 

 

방법 2. 인접한 노드 모두 추가

import sys
input = sys.stdin.readline

N = int(input()) # 컴퓨터 개수
M = int(input()) # 그래프 정보 개수 

graph = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for i in range(N+1):
    graph[i].sort(reverse=True)
    # 인접한 노드가 여러 개일 때 값이 작은 노드부터 방문해주기 위해 내림차순 정렬해주었다. 
    # (문제의 조건은 아니지만 방법 1이랑 비교하기 쉽게 하기 위해서 이렇게 구현함)
    
visit = [False] * (N+1)
stack = [1]
# DFS with stack
while stack:
    v = stack.pop() # 현재 노드
    visit[v] = True # 방문 처리

    for i in graph[v]: # 인접한 노드 조사
        if visit[i] == False:
            stack.append(i) # 방문한 적 없는 노드를 모두 stack에 추가

num = 0
for i in visit:
    if i == True:
        num += 1
print(num-1) # 1번 컴퓨터 제외

 

방법 1과 방법 2 비교

방법 1에서는 노드를 방문했을 때 인접한 노드 하나를 stack에 넣는다. 그리고 stack[-1] 값을 현재 방문한 노드로 둔다. (즉, stack에는 현재 방문한 노드와 그 상위 노드들이 담겨있다. 현재 노드를 방문해온 루트라고 생각하면 이해하기 쉽다.) 

따라서 push 하는 행위가 방문하는 행위이다. pop은 현재 노드에서 더 이상 방문할 노드가 없을 때 수행한다. 

 

방법 2에서는 노드를 방문했을 때 인접한 노드들을 모두 stack에 넣는다. 그리고 pop()을 하여 현재 방문한 노드로 둔다. (즉, stack에는 앞으로 방문해야할 노드들이 담겨있다.) 

따라서 pop 하는 행위가 방문하는 행위이다. 

 

방법 3. 인접한 노드 모두 추가, visit을 스택으로 사용 (대표적인 방법)

방법 2를 조금 수정한 방법

인접한 노드 추가할 때 방문 여부를 확인하는 조건을 없애서 모든 인접한 노드를 추가하고,

현재 노드의 방문 여부를 확인하는 조건을 추가하여 방문한 적 없을 때만 수행하도록 함. 

 

방법 1, 방법 2는 인접한 노드가 여러 개일 때 값이 작은 노드를 먼저 방문하도록 구현한 건데, 사실 그 조건은 안 필요한 경우도 있어서 방법 3은 무작위로 방문하도록 일반화한 방법이기도 함. 

 

방법 3이 구글링했을 때 나오는 방법이다 !

import sys
input = sys.stdin.readline

N = int(input()) # 컴퓨터 개수
M = int(input()) # 그래프 정보 개수 

graph = [[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
visit = [] # 방문한 노드들을 담는 스택
stack = [1]
# DFS with stack
while stack:
    v = stack.pop() # 현재 노드
    if v not in visit: # 방문한 적 없으면
        visit.append(v) # 방문 처리
        stack.extend(graph[v]) # 인접한 노드 모두 stack에 추가

print(len(visit)-1) # 1번 컴퓨터 제외

 

방법 3 이해를 위해 동작 과정을 그려보았다. (graph[i]가 오름차순 정렬되어있다 가정)