BOJ 1260번: DFS와 BFS

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

아주 기본적인 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를 구현하는 방법을 잘 익혀놓자.