[BOJ] 1260 : DFS와 BFS [그래프 이론](Python)

문제 링크

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

1260번: DFS와 BFS

소스 코드

from collections import deque
n,m,v = map(int,input().split())

graph = [[] for _ 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(1,len(graph)):
    graph[i].sort()

# 0부터 n까지 False처리하여 번호를 인덱스로 바로 사용
visited = [False for _ in range(n+1)]
visited[v] = True # 시작점
dfs = [v] # 시작점

def DFS(start):
    # 현 노드에서 방문할 수 있는 모든 노드에 대해
    for node in graph[start]:
        # 아직 방문하지 않은 경우에만
        if not visited[node]:
            visited[node] = True # 방문 처리
            dfs.append(node) # 방문 순서 기록
            DFS(node) # 새 노드를 기준으로 다시 탐색
DFS(v)

# 0부터 n까지 False처리하여 번호를 인덱스로 바로 사용
visited = [False for _ in range(n+1)]
visited[v] = True # 시작점
bfs = [v] # 시작점

def BFS(start):
    queue = deque([start]) # 시작점
    
    while queue: # 큐에 원소가 남아있는 동안 반복
        now = queue.popleft() # 가장 왼쪽 원소 꺼내기
        # 현 노드에서 방문할 수 있는 모든 노드에 대해
        for node in graph[now]:
            # 아직 방문하지 않은 경우에만
            if not visited[node]:
                visited[node] = True # 방문 처리
                queue.append(node) # 큐에 추가
                bfs.append(node) # 방문 순서 기록
BFS(v)

print(*dfs,sep=' ') # 리스트 모든 원소를 공백으로 구분하여 출력
print(*bfs,sep=' ')

 

해설

• DFS, BFS 기초
• 재귀, deque

DFS(Depth-First Search)와 BFS(Breadth-First Search) 비교

아주 기초적인 탐색 알고리즘인 DFS와 BFS입니다.

우리나라 말로는 깊이 우선 탐색과 너비 우선 탐색인데 처음 공부할 때는 잘 와닿지 않는 개념이죠.

오랜만에 이 개념을 다시 접하는 저도 기억이 가물가물해서 직접 그래프를 그려보며 기억을 되살려 봤습니다.

 

문제에 주어진 예제 1을 그래프로 그려보면 다음과 같습니다.

왼쪽이 DFS, 오른쪽이 BFS입니다.

DFS의 경우, 1번 노드에서 출발하고 여기서 이동할 수 있는 가장 작은 번호 2로 이동합니다.

그리고 2번에도 이동할 수 있는 1,4번 노드 중에 1번은 이전에 방문한 곳이므로 무시하고 4로 갑니다.

마지막으로 4에서 이동할 수 있는 1,2,4번 노드 중에 아직 방문하지 않은 3으로 이동하고 마무리 됩니다.

 

BFS의 경우, 1번 노드에서 출발하고 여기서 이동할 수 있는 가장 작은 번호 2로 이동합니다.

그리고 1번 노드에서는 3번으로도 이동할 수 있으므로 이후에 3으로 이동합니다.

1번 노드에서는 4번으로도 이동할 수 있으므로 4번 노드로 이동하는 것이 마지막입니다.

 

이처럼 DFS는 '현재 노드를 기준으로 이동할 수 있는 가장 작은 노드로 이동한 뒤, 그 노드를 기준으로 새출발을 한다'고 할 수 있고,

BFS는 '현재 노드를 기준으로 이동할 수 있는 모든 노드를 작은 것부터 순서대로 방문한 뒤, 그 노드들을 기준으로 새출발을 한다'고 이해할 수 있습니다.

 

DFS

사실 이 문제는 DFS,BFS를 둘 다 적용하기 때문에 하나의 visited를 만들어놓고 재귀함수 내에서 visited를 변경하는 것이 좋겠으나 구현 난이도가 높아서 좀 더 편한 방식을 택했습니다.

논리는 아주 간단합니다.

 

1) 인자로 받은 start를 기준으로 탐색을 수행합니다.

2) start 번호에서 갈 수 있는 node 번호를 graph에서 뽑아냅니다.

3) 이동할 수 있는 node 중에서 아직 방문하지 않은 것을 찾으면 방문 처리를 하고 이를 기준으로 다시 탐색합니다.

4) 현재 노드를 기준으로 연결된 모든 노드가 방문 처리된 경우 탐색이 종료됩니다.

def DFS(start):
    # 현 노드에서 방문할 수 있는 모든 노드에 대해
    for node in graph[start]:
        # 아직 방문하지 않은 경우에만
        if not visited[node]:
            visited[node] = True # 방문 처리
            dfs.append(node) # 방문 순서 기록
            DFS(node) # 새 노드를 기준으로 다시 탐색
DFS(v)

 

BFS

collections의 deque를 활용합니다.

이 큐에 처음 추가한 원소들부터 처리해야 하기 때문인데, 다시 말하면 리스트의 가장 왼쪽 원소를 꺼내어 확인하는 과정이 반복되므로 이 작업에 적합한 자료구조인 deque을 사용하는 것입니다.

(리스트도 가장 앞쪽의 원소를 꺼낼 수 있지만 시간 효율이 낮습니다)

 

1) 시작점을 기준으로 큐를 생성합니다.

2) 큐에 원소가 남아있는 동안, 현재를 나타내는 노드를 큐에서 하나씩 뽑아냅니다.

3) 현재 노드에서 이동 가능한 노드 번호를 graph에서 뽑아냅니다.

4) 아직 방문한 적이 없는 node만 큐에 추가해줍니다.

5) 추가된 노드를 기준으로 위 과정을 반복합니다.

def BFS(start):
    queue = deque([start]) # 시작점
    
    while queue: # 큐에 원소가 남아있는 동안 반복
        now = queue.popleft() # 가장 왼쪽 원소 꺼내기
        # 현 노드에서 방문할 수 있는 모든 노드에 대해
        for node in graph[now]:
            # 아직 방문하지 않은 경우에만
            if not visited[node]:
                visited[node] = True # 방문 처리
                queue.append(node) # 큐에 추가
                bfs.append(node) # 방문 순서 기록
BFS(v)