DFS, BFS

• 그래프에서 모든 간선(edge)의 비용이 동일할 때는 BFS를 이용하여 최단 거리를 찾을 수 있다.

2차원 매트릭스로 푸는 DFS/BFS

• 이 코드는 처음 0번째 인덱스를 0으로 만들어두고 쓴다. 하지만 프로그래머스 문제들은 1 ~ n+1 까지 인덱스가 주어지는게 아니라, 0 ~ n 까지의 그래프가 주어지므로 이에 맞게 습관을 들여서 푸는게 중요해 보임.

코드

from collections import deque

n, m, v = map(int, input().split())
matrix = [[0] * (n+1) for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    
    matrix[a][b] = matrix[b][a] = 1

visit_list = [0] * (n+1)

def dfs(num):
    visit_list[num] = 1
    print(num, end = ' ')
    for i in range(1, n+1):
        if (visit_list[i] == 0 and matrix[num][i] == 1):
            dfs(i)
            
def bfs(num):
    queue = deque([num])
    visit_list[num] = 0
    while queue:
        num = queue.popleft()
        print(num, end = ' ')
        
        for i in range(1, n+1):
            if (visit_list[i] == 1 and matrix[num][i] == 1):
                queue.append(i)
                visit_list[i] = 0

dfs(v)
print()
bfs(v)