DFS와 BFS

문제

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

입력

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

출력

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

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제 입력 2

5 5 3
5 4
5 2
1 2
3 4
3 1

예제 출력 2

3 1 2 5 4
3 1 4 2 5

예제 입력 3

1000 1 1000
999 1000

예제 출력 3

1000 999
1000 999

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

💯 문제 풀이

🔓 문제 접근 과정

먼저 BFS와 DFS의 개념을 알아보자

각각의 개념은 다음과 같다.

BFS와 DFS

너비 우선 탐색(BFS)

너비 우선 탐색(Breadth First Search, BFS)은 탐색을 할 때 너비를 우선으로 하여 탐색하는 알고리즘이다.

너비 우선 탐색은 최단 경로를 찾아준다는 점에서 최단 길이를 보장해야할 때 많이 사용한다.

준비물은 큐이다.

큐는 먼저 들어온것을 먼저 처리를 해준다는 점에서 너비 우선 탐색을 가능하게 해준다.

BFS는 다음과 같은 간단한 알고리즘에 따라서 동작한다.

1. 처음에 시작 노드를 큐에 삽입해준다. 또한 시작 노드를 방문했다고 ‘방문 처리’를 해준다.
2. 큐에서 하나의 노드를 꺼낸다.
3. 해당 노드에 연결돤 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

깊이 우선 탐색(DFS)

깊이 우선 탐색(Depth First Search, DFS)은 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘이다.

깊이 우선 탐색에서는 스택이 사용된다.

DFS는 다음과 같은 간단한 알고리즘에 따라서 작동한다.

1. 처음에 시작 노드를 스택에 삽입하면서 시작한다. 그와 동시에 시작노드를 방문했다고 알리는 ‘방문 처리’를 해주도록 한다.
2. 스택의 최상단 노드를 확인한다.
3. 최상단 노드에게 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 뺀다.

개념을 코드로

하지만 개념만 안다고 코드가 알아서 써지지는 않더라.

이제 개념을 코드로 작성하는데에 알아야 할것들을 알아보자.

먼저 보통 visited라는 변수의 이름으로 배열을 만든다

0으로 채워도 되고, boolean 값으로 넣어도 괜찮다.

이를 바탕으로 dfs와 bfs를 구현하면 되는데

dfs는 재귀를 통해서 쭉 들어간다!의 느낌으로 하면 된다.

bfs는 하나의 기준을 잡고 한줄씩 왔다갔다 한다 의 느낌으로 하면된다.

동기형의 말을 빌리자면

dfs는 E성향라서 일단 파고 bfs는 I성향이라서 약간 천천히 가는것!

이렇게 이해하면 직관적으로 이해할 수 있을것이라 생각한다.

🔑 최종 코드

import sys
input = sys.stdin.readline
number_point, number_edge, start = map(int, input().split())
# 행렬 만들기
graph = [[0]*(number_point+1) for _ in range(number_point+1)]
for i in range(number_edge):
    point_a, point_b = map(int, input().split())
    graph[point_a][point_b] = graph[point_b][point_a] = 1
# 방문 리스트 행렬
visited1 = [0]*(number_point+1)
visited2 = visited1.copy()
def dfs(start):
    visited1[start] = 1
    print(start, end=' ')
    for i in range(1, number_point + 1):
        if graph[start][i] == 1 and visited1[i] == 0:
            dfs(i)
def bfs(start):
    queue = [start]
    visited2[start] = 1
    while queue:
        start = queue.pop(0)
        print(start, end=' ')
        for i in range(1, number_point + 1):
            if (visited2[i] == 0 and graph[start][i] == 1):
                queue.append(i)
                visited2[i] = 1
dfs(start)
print()
bfs(start)

🧑🏻‍💻 이 문제를 풀면서 공부한 내용

15. 너비 우선 탐색(BFS)

16. 깊이 우선 탐색(DFS)