[Python/파이썬] 백준 알고리즘 1260번 - DFS와 BFS

 

 

 

<풀이>

출처 : https://leedaeho1188.tistory.com/38

정점과 간선은 Graph에서 나오는 개념들이다.

정점은 흔히 Vertex라고 부르며 간선은 Edge라고 부른다.

 

전체 풀이 ↓

import sys
from collections import deque

N, M, V = map(int, sys.stdin.readline().rstrip().split())

graph = [[0] * (N + 1) for _ in range(N+1)]
DFS_visited = [False] * (N + 1)
BFS_visited = [False] * (N + 1)

for _ in range(M):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x][y] = 1
    graph[y][x] = 1

def dfs(V):
    DFS_visited[V] = True
    print(V, end=' ')
    for i in range(1, N + 1):
        if not DFS_visited[i] and graph[V][i] == 1:
            dfs(i)

def bfs(V):
    BFS_visited[V] = True
    queue = deque()
    queue.append(V)
    while queue:
        popV = queue.popleft()
        print(popV, end=' ')
        for i in range(1, N + 1):
            if not BFS_visited[i] and graph[popV][i] == 1:
                queue.append(i)
                BFS_visited[i] = True

dfs(V)
print()
bfs(V)

DFS 문제의 경우 대부분 스택과 재귀를 이용하여 문제를 풀 수 있으며, BFS의 경우 큐를 이용하여 풀면 되기에 deque 모듈을 사용하여 풀면 좋다.

 

한 문단씩 끊어서 살펴보겠다.

N, M, V = map(int, sys.stdin.readline().rstrip().split())

graph = [[0] * (N + 1) for _ in range(N+1)]
DFS_visited = [False] * (N + 1)
BFS_visited = [False] * (N + 1)

for _ in range(M):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    graph[x][y] = 1
    graph[y][x] = 1

 

초기화 부분이다. input으로 N, M, V를 각각 받고 graph와 visited 리스트를 초기화해준다.

N이 3이라고 가정하면 graph=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]으로 초기화 되고

DFS_visited와 BFS_visited는 [False, False, False, False]이 된다.

(초기화 할 때 N을 곱하지 않고 N + 1을 곱하는 이유는 리스트의 인덱스는 0부터 시작하기 때문에 편의상 인덱스 0을 버리고 1부터 사용하기 위해서이다.)

 

간선의 방향이 양방향이므로 x->y, y->x 둘 다 생각해야 한다. 따라서 for문을 사용하며 graph[x][y]와 graph[y][x] 둘 다 1을 넣어준다.

(2차원 배열로 graph의 연결을 표현하는 것이다. 연결되어있으면 1, 되어있지 않으면 0이다.)

 

def dfs(V):
    DFS_visited[V] = True
    print(V, end=' ')
    for i in range(1, N + 1):
        if not DFS_visited[i] and graph[V][i] == 1:
            dfs(i)

dfs함수이다. 처음 위치 Vertex의 인덱스 값을 받는다.

그리고 해당 인덱스 값의 DFS_visited[V]를 True로 바꿔 방문했음을 체크한다.

for문과 if문을 사용해 현재 Vertex의 인덱스인 V와 연결되어있고 아직 방문하지 않은 Vertex의 인덱스 값 받아 재귀함수를 사용해 넘어간다.

 

def bfs(V):
    BFS_visited[V] = True
    queue = deque()
    queue.append(V)
    while queue:
        popV = queue.popleft()
        print(popV, end=' ')
        for i in range(1, N + 1):
            if not BFS_visited[i] and graph[popV][i] == 1:
                queue.append(i)
                BFS_visited[i] = True

bfs함수이다. 처음 위치 Vertex의 인덱스 값을 받는다.

여기서도 마찬가지로 BFS_visited[V]를 True로 바꿔 방문했음을 체크한다.

bfs에서는 queue와 while문을 사용한다.

(deque는 양방향에서 pop과 append가 일어날 수 있는 자료구조이다. queue를 사용하는 것보다 시간복잡도가 낮으니 이것을 사용해보도록 하자.)

최초 Vertex의 인덱스 값인 V를 queue에 넣고 while문을 돌린다.

popLeft로 queue에 먼저 들어온 것을 빼내고(FIFO: First In First Out) 그것을 출력한 후 for문과 if문으로 아까 dfs에서 했던 것과 마찬가지로 연결되고 아직 방문하지 않은 Vertex를 찾는다.

그리고 그 Vertex의 인덱스 값을 queue에 넣고 visited 리스트에 방문했음을 체크한다.

 

 

 

<핵심 정리>

1. DFS 문제 : 대부분 스택과 재귀를 이용 / BFS 문제 : 대부분 큐와 while문을 이용

2. queue사용할 때 deque사용해보기

3. graph의 edge 표현은 2차원 배열로 할 수 있다.

4. graph를 표현할 때 인덱스 0번을 비우고 하면 더 편하다.