[백준] 1260번 - DFS와 BFS (DFS, BFS) - 결과 포함

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

이 문제는 DFS와 BFS의 기본적인 구현을 묻는 문제이다.

특징이 있다면 무조건 더 작은 번호부터 출력해야 한다는 것이다.

 

일반적인 DFS와 BFS 함수를 구현하고

방문할 때마다 출력하는 방식으로 문제를 풀었다.

 

작은 수부터 출력하는 문제는 특정 정점을 방문했을 때

그 정점에 인접한 정점 리스트를 정렬한 상태에서

다음 방문을 처리하는 식으로 해결했다.

 

[소스코드]

from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

visited = [False] * n

def dfs(graph, v, visited):
    visited[v] = True
    print(v+1, end=' ')
    graph[v].sort()
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v+1, end=' ')
        graph[v].sort()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

dfs(graph, v-1, visited)
visited = [False] * n
print()
bfs(graph, v-1, visited)

 

DFS와 BFS를 설명하면

그래프의 형태를 가진 데이터를 탐색하는 두 가지 방법이다.

DFS(Depth First Search)는 깊이 우선 탐색으로 한 정점에서 갈 수 있는 가장 먼 곳까지 간 이후에 다시 돌아오는 방법이라고 생각하면 된다.

다음 턴에 갈 수 있는 정점이 존재한다면 무조건 해당 정점을 방문한다. 더 이상 갈 곳이 없다면

이전에 방문했던 정점으로 돌아와서 안 가본 곳으로 이동하면서 모든 정점을 탐색하는 방법이다.

DFS의 방식은 재귀 함수를 이용해서 구현할 수 있다.

선입후출(First-In Last-Out)의 특징을 가진 재귀 함수의 대표적인 예시가 스택(Stack)이라고 할 수 있다. 그러므로 DFS는 스택을 이용해서도 구현할 수 있다.

 

스택에서 정점 하나를 POP해서 이 정점과 인접한 정점들의 방문한 기록을 살펴본다. 방문하지 않은 정점이 존재하면 바로 스택에 PUSH한다.

만약 방문했다면 다시 POP을 하는 방식으로 그래프를 탐색한다.

 

BFS(Breadth First Search)는 너비 우선 탐색으로 DFS와 달리 한 정점에서 갈 수 있는 모든 정점을 방문한다.

현재의 정점에서 갈 수 있는 모든 곳을 먼저 탐색한 이후에 그 다음 정점들을 탐색하는 방식이다.

즉, 먼저 들어온 것을 먼저 처리하는 선입선출(First-In First-Out) 방식을 이용하는데, 이 대표적인 예는 큐(Queue)이다.

 

큐에서 정점 하나를 dequeue해서 해당 정점에 인접한 정점들의 기록을 모두 살핀다. 방문하지 않았던 인접 정점들을 모두 큐에 enqueue한다. 큐에 원소가 존재하지 않을 때까지 반복하면서 그래프를 순회한다.