[백준/Python3] 1260 DFS와 BFS

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

---

풀이

DFS와 BFS를 구현하는 문제다.

DFS

DFS = Depth First Search(깊이우선탐색)으로 root부터 branch 전체를 탐색한 후 다음 branch에 대해 탐색하는 알고리즘이다. DFS는 스택 또는 재귀를 이용해 구현할 수 있다. 본 문제는 재귀를 이용해 해결했다.

어떤 노드를 방문했는지를 저장하는 visited라는 자료구조를 만든다. 이후 visited를 탐색하면서 특정 node를 방문하지 않았다면 그 노드를 방문한다. 이는 아래와 같이 구현할 수 있다.

## 총 N개의 노드가 존재
## graph[target]: target노드에서 연결된 노드를 저장하는 자료구조
## 방문했다면 True, 방문하지 않았다면 False
visited = [False for _ i in range(N)]

def dfs(target):
	visited[target] = True
    for node in graph[target]:
    	if not visited[node]:
        	dfs(node)

BFS

BFS = Breadth First Search(너비우선탐색)으로 root부터 인접한 노드들을 먼저 탐색한 후 인접 노드를 다 방문했다면 그 노드에 대한 인접노드를 같은 방법으로 탐색하는 알고리즘이다. BFS는 queue를 이용해 해결할 수 있다.

무한탐색을 막기위해 DFS와 마찬가지로 어떤 노드를 방문했는지를 저장하는 visited 자료구조를 만든다. queue에 인접 노드 중 방문하지 않은 노드를 모두 저장하고 차례대로 탐색한다. 이때 번호가 클수록 나중에 저장하게 되며 이는 queue의 특성상 나중에 탐색하게 한다. queue가 완전히 빌 때까지 탐색을 진행할 수 있다. 이는 아래와 같이 구현할 수 있다.

## 총 N개의 노드가 존재
## graph[target]: target노드에서 연결된 노드를 저장하는 자료구조
## 방문했다면 True, 방문하지 않았다면 False
visited = [False for _ in range(N)]

def bfs(target):
	visited[target] = True
    queue = deque() # from collections import deque
    queue.append(target)
    
    while queue:
    	next = queue.popleft()
        
       	for node in graph[next]:
        	if not visited[node]:
            	queue.append(node)
                visited[node] = True
        

코드

from collections import deque

# DFS
def dfs(start):
    print(start, end=' ')
    visited[start] = True

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

    return

# BFS
def bfs(start):
    visited[start] = True
    queue = deque()
    queue.append(start)

    while queue:
        target = queue.popleft()
        print(target, end=' ')

        for node in graph[target]:
            if not visited[node]:
                queue.append(node)
                visited[node] = True

    return

# Initial
N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    # 양방향 그래프
    graph[a].append(b)
    graph[b].append(a)

# sort
for i in range(1, N+1):
    graph[i].sort()

# Answer
visited = [False for _ in range(N+1)]
dfs(V)

print()

visited = [False for _ in range(N+1)]
bfs(V)