[백준 문제풀이] 1260번 DFS와 BFS(with. python)

백준 사이트의 1260번에 대한 문제 풀이 입니다. 참고로 저는 파이썬으로 문제를 풀었습니다.
https://www.acmicpc.net/problem/1260

(이 글은 이전에 풀어두었던 문제에 대해 코드 리뷰를 하기 위해 작성되었음을 알려드립니다.)

1260번의 DFS와 BFS의 문제는 다음과 같다.

문제를 풀기 전 DFS와 BFS는 무엇인지 알아야한다. 알고리즘 문제들에서 단골로 출제되는 문제이다. 두 탐색 방법은 같이 알아두면 더 편리하다.

(설명을 위한 그림은 추후에 추가할 예정입니다.)

1. DFS(Depth First Search)

DFS는 흔히 깊이 우선 탐색이라 부르는 알고리즘이다. 그래프가 있을 때 해당 접점을 기준으로 연결되어 있는 접점을 계속해서 타고 들어가는 탐색 방법이다. 아래 그림으로 보면 이해가 더 쉬울 것이다.

2. BFS(Breadth First Search)

BFS는 너비 우선 탐색이라 부른다. 그래프가 있을 때 해당 접점을 기준으로 연결되어 있는 접점을 모두 탐색 한 후 그 중 가장 먼저 탐색한 접점으로 가서 다시 연결되어 있는 모든 접점을 탐색한다. 아래 그래프를 참고하자.

3. 정리 - DFS와 BFS의 차이

두 탐색 방법의 차이는 현재 위치에 있는 접점에서 어느 접점으로 이동하여 탐색을 마저 진행하는 것인가이다.

DFS의 경우 현 위치에서 더 이상 갈 곳이 없을 때까지 접점을 계속 타고 들어간다. 갈 곳이 없어지면 아직 가지 못한 접점과 연결되어 있는 위치로 나와 다시 갈 곳이 없을 때까지 접점을 계속 타고 들어간다. 이를 반복하다가 그래프 상 모든 접점을 방문했다면 탐색이 끝난다.

BFS의 경우 현 위치에서 연결된 모든 접점을 방문한다. 그 접점들을 저장해두고, 가장 먼저 방문했던 접점부터 이를 반복한다. BFS 역시 그래프 상 모든 접점을 방문했다면 탐색이 끝난다.

두 탐색 방법의 차이점을 정리하자면, DFS은 깊이 탐색이기 때문에 해당 위치에서 더이상 갈 수 있는 접점이 없을 때까지 접선을 타고 접점들을 방문한다. 반면에 BFS는 너비 탐색이기 때문에 해당 위치에서 갈 수 있는 모든 접점을 먼저 방문한다. Tree 형태의 그래프로 두 탐색 방법을 더 쉽게 기억할 수 있다. DFS는 현 위치에서 마지막 level까지 방문하고, 거꾸로 타고 올라오면서 마지막 level까지 방문하는 것을 반복한다. BFS는 현 위치에서 다음 level의 모든 노드들을 방문한 후 가장 먼저 방문한 노드로 가서 그 다음 level의 노드들을 모두 방문하는 것을 반복한다.

그러면 이제 백준 문제에 대한 코드 리뷰를 해보도록 하겠다.

4. 문제에 대한 코드 리뷰

# DFS와 BFS

# DFS 탐색에 대한 함수
def dfs(v):
    visit[v] = 1  # 방문했다면 1
    print(v, end=' ')
    for i in range(n+1):
        if visit[i] == 0 and matrix[v][i] == 1:	# 현재 위치와 접선으로 연결되어 있고, 아직 방문하지 않았다면
            dfs(i)  # 재귀함수를 사용하여 탐색하도록 한다.

# BFS 탐색에 대한 함수
def bfs(v):
    queue = [v]
    visit[v] = 0  # DFS를 통해 visit 배열의 모든 값이 1이 되어있음. 따라서 방문했다면 0

    while queue:  # queue에 저장된 값이 없으면 멈춤
        v = queue.pop(0)  # 가장 먼저 들어간 값을 빼내고 v에 저장
        print(v, end=' ')
        for i in range(n+1):
            if visit[i] == 1 and matrix[v][i]:	# 접점 i에 아직 방문하지 않았고, v와 연결되어 있으면
                queue.append(i)	# 나중에 다시 방문하여 연결된 모든 접점에 방문하기 위해 queue에 저장
                visit[i] = 0	# i에 방문했다면 0

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

# 배열의 크기를 n+1로 설정해두는 이유 - 모든 배열은 index가 0부터 시작. 하지만 문제에선 접점이 1부터 시작하여 헷갈리지 않도록 하기위해 n+1로 설정
matrix = [[0]*(n+1) for i in range(0, n+1)]
for i in range(m):
    a, b = map(int, input().split())
    matrix[a][b] = 1
    matrix[b][a] = 1

# 방문했는지 확인하기 위한 배열
visit = [0]*(n+1)

dfs(v)
print()
bfs(v)