[Python] 백준 1260번: DFS와 BFS

1260번: DFS와 BFS

 

🐰 문제

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

🐰 입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

🐰 출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

🥕 DFS

인접 행렬, Stack
인접 행렬, 재귀 함수
인접 리스트, Stack
인접 리스트, 재귀 함수

1️⃣ 인접 행렬, Stack

N, M, V = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 정점
dfs_visited = [False] * (N + 1)

# 인접 행렬
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1

# 스택
def dfs():
    stack = [V]
    
    while stack:
        value = stack.pop()
        
        if not dfs_visited[value]: # 방문하지 않은 노드일 경우 출력
            print(value, end = ' ')
            dfs_visited[value] = True
        
        # stack에 3 < 2 < 1 순서로 저장되어야 1부터 pop 된다
        for j in range(len(matrix[value]) - 1, - 1, - 1):
            if matrix[value][j] == 1 and not dfs_visited[j]: # 현재 노드와 연결되어 있고 방문하지 않은 경우
                stack.append(j)
                
dfs()

 

2️⃣ 인접 행렬, 재귀 함수

재귀 함수는 앞선 프로세스가 스택으로 쌓이는 형태가 된다. 코드가 간결하다.

# 재귀 함수
def dfs(v):
    dfs_visited[v] = True
    print(v, end = ' ')
    
    for j in range(len(matrix[v])):
        if matrix[v][j] == 1 and not dfs_visited[j]: # 현재 노드와 연결되어 있고, 방문하지 않은 경우
            dfs(j)
                
dfs(V)

 

3️⃣ 인접 리스트, Stack

N, M, V = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 정점
dfs_visited = [False] * (N + 1)

# 인접 리스트
graph = [[]] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    if graph[a] == []: # 비어 있을 경우 append() 메서드를 사용할 수 없다
        graph[a] = [b]
    else:
        graph[a].append(b)
    if graph[b] == []:
        graph[b] = [a]
    else:
        graph[b].append(b)

# 스택
def dfs(v):
    stack = [v]
    
    while stack:
        now = stack.pop()
        if not dfs_visited[now]:
            print(now, end = ' ')
            dfs_visited[now] = True
    
        for i in graph[now]:
            if not dfs_visited[i]:
                stack.append(i)
            
for i in graph:
    i.reverse()

dfs(V)
print()

 

4️⃣ 인접 리스트, 재귀 함수

N, M, V = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 정점
dfs_visited = [False] * (N + 1)

# 인접 리스트
graph = [[]] * (N + 1)
for _ in range(M):
    a, b = map(int, input().split())
    if graph[a] == []: # 비어 있을 경우 append() 메서드를 사용할 수 없다
        graph[a] = [b]
    else:
        graph[a].append(b)
    if graph[b] == []:
        graph[b] = [a]
    else:
        graph[b].append(b)
    
# 재귀 함수
def dfs(v):
    dfs_visited[v] = True
    print(v, end = ' ')
    
    for j in graph[v]:
        if not dfs_visited[j]: # 연결된 요소를 for문으로 돌리므로 연결되어 있는지 확인할 필요가 없다
            dfs(j)

dfs(V)

 

🥕 BFS

인접 행렬, Queue
인접 리스트, Queue

1️⃣ 인접 행렬, Queue

from collections import deque

N, M, V = map(int, input().split()) # 정점 개수, 간선 개수, 탐색 시작 정점
bfs_visited = [False] * (N + 1)

# 인접 행렬
matrix = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    matrix[a][b] = matrix[b][a] = 1

# Queue
def bfs(v):
    bfs_visited[v] = True
    
    queue = deque()
    queue.append(v)
    
    while queue:
        now = queue.popleft()
        print(now, end = " ")
        
        for i in range(1, N + 1):
            if not bfs_visited[i] and matrix[now][i] == 1:
                queue.append(i)
                bfs_visited[i] = True
                
bfs(V)

 

2️⃣ 인접 리스트, Queue

def bfs(v):
    queue = deque()
    queue.append(v)
    
    while queue:
        now = queue.popleft()
        
        if not bfs_visited[now]:
            print(now, end = " ")
            bfs_visited[now] = True
            
            for j in graph[now]:
                queue.append(j)
                
bfs(V)

 

Tree와 Graph | 이진 트리와 이진 탐색 트리(BST: Binary Search Tree)

[그래프 탐색] BFS / DFS