[백준] 1260번 DFS와 BFS 다시 풀기

import sys
from collections import deque

N, M, V = map(int,sys.stdin.readline().split())

#graph 입력 받기
graph = [[0]* (N+1) for i in range(N+1)]
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a][b] = graph[b][a] = 1

dfs_visited = [0] * (N+1)
def dfs(start_Node):
    dfs_visited[start_Node] = 1
    print(start_Node, end = ' ')
    for i in range(1, N+1):
        if dfs_visited[i] == 0 and graph[start_Node][i] == 1:
            dfs(i)

bfs_visited = [0] * (N+1)
def bfs(start_Node):
    queue = deque()
    queue.append(start_Node)
    bfs_visited[start_Node] = 1
    while queue:
        start_Node = queue.popleft()
        print(start_Node, end= ' ')
        for i in range(1, N+1):
            if bfs_visited[i] == 0 and graph[start_Node][i] == 1:
                queue.append(i)
                bfs_visited[i] = 1

dfs(V)
print()
bfs(V)

 

graph를 받을 때 undirected graph라서 양쪽으로 모두 연결시켜주어야 한다.

DFS

먼저 파라미터로 받은 start_Node를 방문처리하고, 출력한다. 그리고 graph에서 start_Node와 연결되어 있고 방문하지 않은 노드로 다시 dfs를 수행한다.

BFS

deque로 큐를 만들고, start_Node를 큐에 넣는다. 그리고 출력한다. start_Node와 연결되어 있고 방문하지 않은 노드는 큐에 넣고, 방문처리한다.