[백준][DFS/BFS] DFS와 BFS (+ 재귀 함수가 아닌 반복문을 이용한 DFS, 우선순위 큐를 이용한 인접 리스트)

오늘의 학습 키워드

DFS, BFS, 스택, 큐, 우선순위 큐

 

오늘의 회고

🌱 오늘의 문제

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

 

그래프를  DFS와 BFS로 탐색한 결과를 출력하는 문제이다.

방문 가능한 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다.

 

 

🌱 나의 시도

1. 인접 리스트 구현

그래프를 나타내기 위해 우선순위 큐를 이용한 인접 리스트를 구현하였다.

이 문제에서는 방문 가능한 정점이 여러 개인 경우 정점 번호가 작은 것부터 순회하여야 하기 때문에, 인접 리스트 내부 인덱스는 정렬된 상태로 유지되어야 한다. 우선순위 큐는 힙으로 구현되어 항상 정렬된 상태를 유지하며 삽입/삭제 시 O(log N)의 시간 복잡도를 가지므로, 리스트를 정렬하는 것보다 우선순위 큐를 이용하는 것이 시간 복잡도 측면에서 더 효율적일 것이라고 판단하였다.

n, m, v = map(int, input().split())

# 우선순위 큐를 이용하여 가장 작은 노드부터 고려
adj_list_bfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1
adj_list_dfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1

for _ in range(m):
    st, en = map(int, input().split())
    adj_list_bfs[st].put(en)
    adj_list_bfs[en].put(st) # 양방향 그래프
    adj_list_dfs[st].put(en)
    adj_list_dfs[en].put(st) # 양방향 그래프

 

이 문제에서는 BFS, DFS 두 함수에 인접 리스트가 필요하다.

그러나 인접 리스트가 2차원 배열이라 얕은 복사 방식으로는 배열을 복사할 수 없었다.

copy 모듈의 deepcopy 함수를 사용하니 컴파일 에러가 발생하여 리스트를 각각 생성해주었다.

슬라이싱 방식으로 깊은 복사도 가능하다고 하는데, 복사를 하는 것과 동일한 배열 두 개 만드는 것 중 어느 것이 더 나을지 모르겠다.

 

(혹시 이 글을 보는 분 중 이 부분을 더 효율적으로 구현할 수 있는 방법을 아신다면 부디 알려주세요 🥹)

 

 

 

2. 반복문을 이용한 DFS 구현

이전에 재귀 함수를 이용해서 DFS를 구현했다가 RecursionError를 마주한 경험이 있다.

그 때는 sys의 setrecursionlimit()를 이용하여 재귀 함수의 허용 범위를 늘려주었다. (참고: https://developer-zoyh.tistory.com/18)

[백준][DFS] 99클럽 코테 스터디 4일차 TIL + 안전 영역 (+ RecursionError 핸들링 하기)

 

그러나 실제 환경에서는 허용 범위를 늘리는 것이 아니라 제한된 메모리 환경 내에서 구현할 수 있어야 한다고 생각하여 반복문으로 DFS를 구현해보았다.

 

재귀 함수를 호출할 때에는 고려해주지 않아도 되었던 아래 포인트들을 집중 공략해서 구현해보았다.

1. Stack에서 노드를 제거하는 시점

2. 방문 처리하는 시점

3. 현재 노드를 전환해주는 시점

 

특히, 특정 노드에서 더 이상 방문하지 않은 인접 노드가 없어 스택에서 제거하게 된 경우, 스택에 남아있는 노드 중 최상단 값으로 현재 노드를 변경해주어야 한다. (이 부분을 빼먹어서 한 번 틀렸다..ㅎㅎ)

def dfs(v, adj_list):
    answer = str(v)
    c_node, stack = v, [v] # 시작 노드
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while stack:
        while True:
            # 방문하지 않은 인접 노드가 없는 경우
            if adj_list[c_node].empty(): 
                stack.pop()
                if stack: c_node = stack[-1]
                break

            n_node = adj_list[c_node].get()
            if not visited[n_node]:
                stack.append(n_node)
                answer += f' {n_node}'
                visited[n_node] = True
                c_node = n_node
                break
                
    return answer

 

 

이전에 정리했던 DFS의 동작 방식을 보면서 코드를 구현하니 머리로만 생각할 때보다 쉽게 접근할 수 있었다.

(참고: https://developer-zoyh.tistory.com/17)

[알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)

 

 

3. BFS 구현

DFS를 확실히 이해하고 나니 BFS를 구현하는 것은 어렵지 않았다.

이전에 개념 정리하면서 BFS 코드를 한 번 구현해 보기도 하였고, 현재 노드를 기준으로 인접 노드를 모두 배열에 넣으면 되어서 그런지 구현 난이도가 쉽게 느껴졌다.

def bfs(v, adj_list):
    answer = ''
    que = deque([v])
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while que:
        c_node = que.popleft()
        answer += f'{c_node} '

        while not adj_list[c_node].empty():
            n_node = adj_list[c_node].get()
            if not visited[n_node]: 
                que.append(n_node)
                visited[n_node]=True
    
    return answer

 

 

4. 최종 코드

최종적으로 아래와 같이 코드를 완성하였다.

dfs, bfs를 각 함수로 정의하였고, 각 함소를 호출할 때 시작 노드 v와 인접 리스트를 함수에 파라미터로 전달하였다.

dfs는 스택, bfs는 큐와 함께 구현하였으며 두 코드 모두 반복문을 사용하였다.

 

from queue import PriorityQueue
from collections import deque

def dfs(v, adj_list):
    answer = str(v)
    c_node, stack = v, [v] # 시작 노드
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while stack:
        while True:
            # 방문하지 않은 인접 노드가 없는 경우
            if adj_list[c_node].empty(): 
                stack.pop()
                if stack: c_node = stack[-1]
                break

            n_node = adj_list[c_node].get()
            if not visited[n_node]:
                stack.append(n_node)
                answer += f' {n_node}'
                visited[n_node] = True
                c_node = n_node
                break
                
    return answer

def bfs(v, adj_list):
    answer = ''
    que = deque([v])
    
    visited = [False]*(n+1) # 인덱스 직접 접근을 위해 +1
    visited[v] = True

    while que:
        c_node = que.popleft()
        answer += f'{c_node} '

        while not adj_list[c_node].empty():
            n_node = adj_list[c_node].get()
            if not visited[n_node]: 
                que.append(n_node)
                visited[n_node]=True
    
    return answer

''' MAIN 구현부 '''

n, m, v = map(int, input().split())

# 우선순위 큐를 이용하여 가장 작은 노드부터 고려
adj_list_bfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1
adj_list_dfs = [PriorityQueue(maxsize=n) for _ in range(n+1)] # 인덱스 직접 접근을 위해 +1

for _ in range(m):
    st, en = map(int, input().split())
    adj_list_bfs[st].put(en)
    adj_list_bfs[en].put(st) # 양방향 그래프
    adj_list_dfs[st].put(en)
    adj_list_dfs[en].put(st) # 양방향 그래프


print(dfs(v, adj_list_bfs))
print(bfs(v, adj_list_dfs))

 

 

오늘의 후기

드디어 재귀 함수를 사용하지 않고 DFS를 구현할 수 있게 되었다!

RecursionError가 발생하는 게 찝찝했는데 드디어 해결할 수 있게 되어서 기쁘다.

 

또 우선순위 큐, 덱, 스택과 같이 기존에 개념으로만 이해하고 있던 자료구조들을 직접 코드를 통해 다뤄보게 되어 반갑고 좋았다.

앞으로 익숙해질 수 있도록 자주 활용해보려고 한다.