백준 BOJ 1260번 DFS와 BFS - Python 풀이

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

소스 코드

import sys, collections

"""def DFS(graph, v):
    visited=[False] * (n+1)
    s=deque()
    s.appendleft(v)
    while(s):
        if(visited[s[0]]==False):
            print(s[0],end=" ")
            visited[s[0]]=True
            for i in graph[s[0]]:
                if(visited[i]==False):
                    s.appendleft(i)
                    break
        else:
            s.popleft()
    print()
"""


def DFS(v):
    visited[v] = True
    print(v, end=" ")
    for i in graph[v]:
        if visited[i] == False:
            DFS(i)


def BFS(v):
    visited = [False] * (n + 1)
    q = collections.deque()
    q.append(v)
    visited[v] = True
    while q:
        for i in graph[q[0]]:
            if visited[i] == False:
                q.append(i)
                visited[i] = True
        print(q.popleft(), end=" ")


# n = 정점개수, m = 간선개수, v = 시작정점, graph = 정점과 간선을 저장하는 배열
n, m, v = map(int, sys.stdin.readline().split())
graph = [[] for i in range(n + 1)]
visited = [False] * (n + 1)

# 두 정점을 잇는 간선 입력
for i in range(m):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1].append(v2)
    graph[v2].append(v1)

# 작은 순서대로 정렬 (오름차순)
for i in range(n + 1):
    graph[i] = sorted(graph[i])

# DFS, BFS 호출
DFS(v)
print()
BFS(v)

이 문제는 개념 문제에 가깝다. 그래서 문제에 대해 해설할게 없고 개념적인 부분을 학습해야 풀 수 있다.

너비 우선 탐색(BFS, Breadth First Search)와 깊이 우선 탐색(DFS, Depth First Search) 알고리즘을 알고 있어야 한다.

(선행 지식으로 기본적인 자료구조인 스택(Stack)과 큐(Queue), 그리고 재귀 호출을 알고 있어야 한다.)

 

https://en.wikipedia.org/wiki/Breadth-first_search#/media/File:Animated_BFS.gif

Breadth-first search - Wikipedia

https://en.wikipedia.org/wiki/Depth-first_search#/media/File:Depth-First-Search.gif

Depth-first search - Wikipedia

우선 두 그래프 탐색 알고리즘의 차이를 애니메이션을 통해 확인해보고

 

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog

BFS와 DFS를 키워드로 검색하여 여러 블로그에서 설명하는 개념을 쭉 읽어본 뒤

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as explored
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as explored then
11                  label w as explored
12                  w.parent := v
13                  Q.enqueue(w)

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

이해한 개념을 바탕으로 수도 코드를 읽어본다.

수 많은 예시 코드가 있지만 결국 수도 코드를 각 언어 문법에 맞게 옮겨놓은 것 뿐이다.

수도 코드에 잘 나와있듯이, BFS는 큐를 통해, DFS는 재귀 또는 스택을 통해 구현한다.

두 가지 방법 중 하나를 먼저 이해한 뒤 다른 방법도 시도하는 것이 좋다.

 

그럼 파이썬 문법에 맞게 수도 코드를 파이썬 코드로 옮겨본다.

그 다음 예시 코드와 비교해보고 틀린 부분을 고쳐보면 된다.