[백준 1260번] DFS와 BFS

from collections import deque

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

graph = [[] for _ in range(n+1)]

visited_dfs = [False] * (n+1)
visited_bfs = [False] * (n+1)

# 노드와 간선 정보 받기
for _ in range(m):
    x, y = map(int,input().split())
    graph[x].append(y)
    # 두 정점 사이의 간선은 양방향이므로 양방향으로 저장
    graph[y].append(x)

# 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것 부터 방문해야 하므로
# 각 노드마다 정렬
for i in graph:
    i.sort()

# DFS 함수 구현
def dfs(graph,start,visited):
    
    visited[start] = True

    print(start, end=" ")

    for i in graph[start]:
        if not visited[i]:
            dfs(graph,i,visited)

# BFS 함수 구현
def bfs(graph,start,visited):

    visited[start] = True

    queue = deque([start])
    
    while queue:
        node = queue.popleft()

        print(node, end=" ")

        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
    
dfs(graph,v,visited_dfs)
print()
bfs(graph,v,visited_bfs)

 

이번 문제는 DFS와 BFS 알고리즘을 이해하고, 구현해낼 수 있는지 물어보는 대표적인 문제라고 할 수 있다.

 

아무래도 DFS와 BFS 알고리즘의 동작 방식은 이해하고 있었지만 코드 작성에 어색했던 나는 대표적인 기본문제부터 풀어보고자 이 문제를 풀어보자고 결심하게 되었던 것 같다.

 

이 문제의 핵심은 DFS 알고리즘은 재귀함수를 사용하여 스택 자료구조를 통해 최대한 깊은 노드부터 탐색하는 것이고, BFS 알고리즘은 deque 라이브러리를 사용하여 큐 자료구조를 통해 인접한 노드부터 탐색하는 것을 이해하고 있어야 한다는 것이다.

 

공부했던 DFS와 BFS 함수를 구현하는 것은 크게 어렵지 않았는데, 문제를 풀다보니 몇몇 테스트케이스에서 제대로 값이 나오지 않았었다.

 

다시 문제를 확인해보니 다음과 같은 중요한 2가지 조건이 존재했다.

1. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다.
2. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

먼저 첫번째 조건은 정점에 여러 개의 다른 정점이 연결되어 있다면, 번호가 작은 것을 먼저 방문해야 한다는 조건인데 이를 만족시켜주기 위해 다음과 같이 각 정점의 간선정보를 저장하는 graph 2차원 리스트를 각 정점마다 오름차순으로 정렬해주었다.

# 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것 부터 방문해야 하므로
# 각 노드마다 정렬
for i in graph:
    i.sort()

 

 

두번째 조건은 입력으로 주어진 두 정점 사이에 간선은 양방향으로 연결되어 있다는 것인데, 이를 만족 시켜주기 위해서 다음과 같이 간선 정보를 입력받을 때 양방향으로 저장해주었다.

# 노드와 간선 정보 받기
for _ in range(m):
    x, y = map(int,input().split())
    graph[x].append(y)
    # 두 정점 사이의 간선은 양방향이므로 양방향으로 저장
    graph[y].append(x)

 

만약에 테스트케이스 1번은 통과되었는데, 2번 3번이 통과되지 않는다면 위 조건이 누락되지 않았는지 점검해보면 좋을 것 같다.

 

DFS와 BFS에 대한 개념과 동작방식을 확실히 이해하고 구현까지 해볼 수 있었던 좋은 문제였다 :)