아주 기본적인 DFS, BFS 구현 문제이다.
백준 기록 보면 인접리스트로 푼 것과 인접배열로 푼 것 두 가지 방식을 확인할 수 있다.
dfs를 구현하는 방식에는 재귀함수로 구현하는 방법과 스택을 이용하는 방법 두 가지가 있는데, 이 문제에서는 정점번호가 작은 순서대로 출력해야해서 재귀함수로 구현하는 방법이 더 나을 것 같아 그렇게 풀었지만, 코드는 일단 올려놓는다.
(dfs2 함수는 정점번호가 작은 순서대로 출력되지 않는다.)
import sys
from collections import deque
N, M, V = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N+1)]
for _ in range (M):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
#정점 번호가 작은 것부터 방문하기 위해
for i in range(1,N+1):
graph[i].sort()
#재귀함수로 구현한 dfs
check = [False]*(N+1)
def dfs1(x):
check[x] = True
print(x, end=" ")
for i in graph[x]:
if (check[i]==False):
dfs1(i)
#스택으로 구현한 dfs
def dfs2(x):
stack = []
visit = [False]*(N+1)
visit[x] = True
stack.append(x)
while(stack):
now = stack.pop()
print(now, end=" ")
for i in graph[now]:
if (visit[i]==False):
stack.append(i)
visit[i] = True
#큐로 구현한 bfs
def bfs(x):
q = deque()
visit = [False]*(N+1)
q.append(x)
visit[x] = True
while(q):
now = q.popleft()
print(now, end=" ")
for i in graph[now]:
if (visit[i]==False):
q.append(i)
visit[i] = True
dfs1(V)
print()
bfs(V)
dfs와 bfs를 구현하는 방법을 잘 익혀놓자.
'알고리즘💻 > 그래프(DFS&BFS)' 카테고리의 다른 글
BOJ 2606번: 바이러스 (0) | 2021.02.08 |
---|---|
5829번: Luxury River Cruise (0) | 2021.02.08 |
BOJ 19538번: 루머 (0) | 2021.02.07 |
BOJ 1697번: 숨바꼭질 (0) | 2021.02.06 |
BOJ 16953번: A → B (0) | 2021.02.06 |