DFS와 BFS - 1260번

DFS는 재귀로 구현하고, BFS는 스택으로 구현한다.

먼저 그래프를 만들어준다.

 

 

DFS

방문했던 곳을 체크하기위한 배열을 준비한다.

방문시 방문했다고 표시한다.

그 다음 방문한 곳의 그래프를 검사하여 방문하지 않은 곳을 DFS함수에 넣어서 재귀적으로 탐색을 진행한다.

 

BFS

방문했던 곳을 체크하기위한 배열을 준비한다.

방문시 방문했다고 표시한다. 

방문한 곳을 스택에 넣는다.

 

스택에서 꺼내서 출력을 한다.

꺼낸 것의 그래프를 탐색하여 아직 방문하지 않은 곳을 스택에 넣는다.

스택이 빌 때까지 반복하면 모든 끝까지 탐색할 수 있다.

 

import queue
import sys
from collections import deque

input = sys.stdin.readline

nodes, edges, start = map(int,input().split())

graph = [[] for _ in range(nodes + 1)]

for i in range(edges):
    a,b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1, nodes+1):
    graph[i].sort()

visited = [False] * (nodes + 1)

def DFS(start):
    nd = start
    visited[nd] = True
    print(nd, end = ' ')
    for i in graph[nd]:
        if not visited[i]:
            DFS(i)

def BFS(start):
    nd = start
    queue = deque([nd])
    visited[nd] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

DFS(start)
print()
visited = [False] * (nodes + 1)
BFS(start)