[백준 1260번] [Python] DFS와 BFS (그래프 탐색)

이미 학교에서 배운 부분이지만 오랜만에 코딩을 하려고 하니 기억이 안났다.

DFS, BFS는 다른 문제를 풀기 위해서도기본적이고 중요한 개념라고 생각하여 이 문제를 먼저 풀게 되었다.

 

[문제]

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

 

[내 코드]

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

graph = [[] for i in range(n+1)]
visited = [False] * (n+1)

for j in range(1, m+1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

graph = list(map(sorted, graph))

def DFS(graph, v, visited):
    visited[v] = True
    print(v, end=' ')

    for k in graph[v]:
        if not visited[k]:
            DFS(graph, k, visited)

DFS(graph, v, visited)
print("")

#BFS
from collections import deque

visited = [False] * (n+1)
def BFS(graph, root, visited):
    queue = deque([root])
    visited[root] = True
    
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

BFS(graph, v, visited)

사실 DFS, BFS를 다시 공부한다는 목적으로 문제를 풀었기 때문에 구글링을 하며 코딩을 하였다.

 

가장 중요한 개념은 DFS는 재귀함수를, BFS는 deque를 사용한다는 점이다.

 

[DFS와 BFS 차이]

 

DFS는 깊이 우선 탐색이기 때문에 인접한 방문하지 않은 노드가 있으면 계속 하여 방문하고 이미 방문한 노드밖에 없는 경우엔 최상단 노드로 돌아가 다시 인접한 방문하지 않은 노드가 있는지 탐색하는 것이다.

 

DFS 동작 과정

1. 첫번째 노드 방문 표시

2. 첫번째 노드의 인접노드가 방문하지 아직 않은 경우 해당 인접노드를 인자로 갖는 재귀함수 호출 - 반복

3. 방문하지 않은 인접 노드가 없는 경우 재귀함수는 호출되지 않고 최상단 노드로 돌아감

4. 최상단 노드의 방문하지 않은 인접노드가 있는 경우 재귀함수 호출 - 반복

5. 모든 노드를 방문한 경우 재귀함수 종료

 

BFS는 넓이 우선 탐색으로 가까운 노드부터 탐색하는 탐색 알고리즘이다.

 

BFS 동작 과정

1. 첫번째 탐색 노드를 스택에 넣고 방문 표시

2. 탐색 노드와 인접한 노드가 있으면 스택에 넣고 방문표시, 더이상 없으면 스택 최상단의 노드 꺼내기

3. 반복

 

이렇게만 문제를 풀 경우에는 두 번째 테스트 케이스에 통과하지 못한다. 이 문제는 그래프가 정렬된 뒤 탐색한 결과를 원하기 때문이다. 

graph = list(map(sorted, graph))

그렇기에 map함수를 이용해 graph의 모든 요소를 정렬한 뒤 list함수를 사용해 자료형을 리스트로 바꾸었다.

다음에도 써먹을 수 있을것 같다.