[알고리즘] DFS & BFS 연습

DFS와 BFS에 대한 개념을 좀 더 숙달하기 위해서 백준 문제를 풀다가

두 가지의 방법을 모두 써서 풀어야하는 문제가 있어서 가져와 보았다.

백준 1260번 - DFS와 BFS

문제 설명

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

처음에 정점의 개수, 간선의 개수, 탐색을 시작할 번호가 주어지는데 간선의 개수만큼 간선이 연결하는 정점의 번호를 입력받은뒤에 DFS를 수행한 결과와 BFS를 수행한 결과를 출력하면 되는 문제이다.

이제 입력받는 것은 익숙하니까 미리 적어보면

import sys
from collections import defaultdict

N, M, V = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for _ in range(M):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

그래프는 서로 연결되어있다는 뜻으로 방향없이 넣어주었다.

이제 DFS와 BFS의 탐색을 해주는 함수를 만들 예정인데 입력과 출력의 예제를 보면

출력의 첫번째 줄이 DFS이고 두번째 줄이 BFS인데 방문할 수 있는 정점이 여러개인 경우에는

정점의 번호가 작은 노드를 먼저 방문하라는 조건이 있었기 때문에 DFS같은 경우에 재귀함수를 쓰기로 했다.

def dfs_recursive(node, visited):
    visited.append(node)
    graph[node].sort()
    for adjacent in graph[node]:
        if adjacent not in visited:
            dfs_recursive(adjacent, visited)
    return visited

스택을 사용할 경우에 그래프를 그림으로 그렸을 때, 왼쪽이 아닌 오른쪽 부터 탐색하기 때문에

재귀함수를 쓰기로 마음먹었고 작은 노드를 먼저 방문하라는 조건 때문에 sort로 정렬을 해주었다.

def bfs_queue(start):
    visited = [start]
    q = deque([start])
    while q:
        node = q.popleft()
        graph[node].sort()
        for adjacent in graph[node]:
            if adjacent not in visited:
                q.append(adjacent)
                visited.append(adjacent)
    return visited

BFS 같은 경우에는 역시 deque를 사용하여 양방향 큐를 만들어 준 후에

똑같이 정렬해서 리스트의 왼쪽부터 빼내어 BFS 탐색을 구현할 수 있도록 했다.

 

※ 최종코드

import sys
from collections import deque, defaultdict


def dfs_recursive(node, visited):
    visited.append(node)
    graph[node].sort()
    for adjacent in graph[node]:
        if adjacent not in visited:
            dfs_recursive(adjacent, visited)
    return visited


def bfs_queue(start):
    visited = [start]
    q = deque([start])
    while q:
        node = q.popleft()
        graph[node].sort()
        for adjacent in graph[node]:
            if adjacent not in visited:
                q.append(adjacent)
                visited.append(adjacent)
    return visited


N, M, V = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
for _ in range(M):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)
print(' '.join(map(str, dfs_recursive(V, []))))
print(' '.join(map(str, bfs_queue(V))))

이제 어느정도 문제푸는데에 자신감이 붙었지만

그래프를 만드는데 있어서 인접 리스트가 아닌 인접 행렬로 되어있는 문제를 풀 때 어려운 문제가 있었다. 

왠만한건 직접 찾아보려고 하지만 부트캠프중에 튜터님이 계시는데 안 물어보는 것도 실례인 것 같아서

지금까지 궁금했던 점들을 모아서 찾아가서 물어봐야 겠다.