해당 포스팅은 나동빈 저자님의 "이것이 취업을 위한 코딩테스트다 with Python" 책을 참고한 글입니다.
이번 포스팅에서는 BFS/DFS 관련 문제 풀이 리뷰를 진행해보려고 합니다!
문제 리뷰를 시작하기 전에 이번에 DFS와 BFS를 학습하고 문제를 풀어보면서 가장 어려웠던 부분이 있었다.
바로 문제를 일고 본격적으로 풀이를 시작할 때 DFS를 써야해? BFS를 써야해? 라는 생각이 너무너무 많이 들었다.
그래서 간단하게 언제 BFS를 써야하고 DFS를 써야하는지에 대해 정리해보려고 한다.
1. BFS와 DFS는 언제써요?
BFS와 DFS의 개념이 잘 이해가 안되시는 분들은 구글링 또는 저의 깃헙을 통해 확인해주세용!
나 같이 코딩테스트 공부를 본격적으로 시작한지 얼마 되지 않은 취준생 분들은 문제를 아무리 봐도 BFS를 써야하는지 DFS를 써야하는지 결단이 안날 것이라고 감히 예상해본다.
먼저 그래프의 모든 정점을 방문하는 것이 중요한 문제가 있다. 단순하게 모든 노드를 방문하는 것이 중요한 문제라면 DFS나 BFS 어떤 방법이든 사용해도 괜찮다고 한다!
BFS는 너비우선탐색으로 현재 나의 위치에서 가장 가까운 노드를 먼저 방문하는 것이 특징입니다.
노드를 방문하면서 현재 위치를 Queue에서 pop해주고 방문한 곳은 체크한 뒤 방문할 곳을 Queue에 push하는 과정이다.
그렇기 때문에 미로 탐색과 같은 알고리즘은 최단 거리만을 가지고 탈출하기 때문에 BFS가 적절하다!
하지만 미로탐색을 진행하는데 이동할 때마다 가중치가 붙어서 이동한다거나 이동과정에서 여러 제약이 있을 경우에는 DFS로 구현하는 것이 좋다. BFS보다는 탐색시간이 더 걸리긴 하지만 가중치에 대한 변수를 지속해서 관리할 수 있다는 장점이 있다.
2. 음료수 얼려먹기 문제 리뷰
문제
N × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.
구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.
이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하라.
다음의 4 × 5 얼음 틀 예시에서는 아이스크림이 총 3개가 생성된다
입력
- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 <= N, M <= 1,000)
- 두 번째 줄부터 N + 1 번째 줄까지 얼음 틀의 형태가 주어진다.
- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.
출력
- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
입력예시 1
4 5
00110
00011
11111
00000출력예시 1
3입력예시 2
15 14
00000111100000
11111101111110
11011101101110
11011101100000
11011111111111
11011111111100
11000000011111
01111111111111
00000000011111
01111111111000
00011111111000
00000001111000
11111111110011
11100011111111
11100011111111출력예시 2
8리뷰 및 풀이
BFS/DFS에 대해 어느정도 개념을 잡고 시도를 한 첫 문제이다. 아니나 다를까 어떤 방법을 써야할지 진짜 30분을 넘게 고민하다가 결국 잘못된 방법을 선택했고 갈팡질팡하다가 못푼 문제이다...!
그렇기 때문에 이 문제는 책의 해설을 정리해보려고 한다!
- 위에서 정리했다시피 이동과정에서 여러 제약이 있는 문제이기 때문에
DFS를 선택하는 것이 중요하다!- 특정 지점의 주변 상하좌우를 살펴본 뒤에 주변 지점중에서 값이 0이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상하좌우를 살펴보면서 방문을 다시 진행해보면 연결된 모든 지점을 방문할 수 있다.
- 2~3번의 과정을 모든 노드에 반복하면서 방문하지 않은 지점의 수를 센다.
- 즉, DFS 함수가 실행된 횟수가 개수이다.
# DFS와 BFS PART2 실전문제) 음료수 얼려먹기
N, M = map(int, input().split())
graph = [list(map(int, input())) for _ in range(N)]
# DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들 방문
def dfs(x, y):
# 좌표가 범위 벗어나면 종료
if x <= -1 or x >= N or y <= -1 or y >= M:
return False
# 현재 노드를 방문하지 않음
if graph[x][y] == 0:
graph[x][y] = 1 # 방문처리
# 상하좌우 모두 재귀적으로 DFS 함수 호출
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
return True
return False
result = 0
for i in range(N):
for j in range(M):
if dfs(i, j) == True:
result += 1
print(result)위의 코드에서 DFS 4번 실행하는 부분이 있다. 이 부분은 재귀를 이해해야 이해가 가능한 코드이다.
재귀를 이해하기가 너무 힘들어서 노트 1장 뜯어서 모든 과정을 싹다 그렸다.
그리다보면 DFS 4개가 모두 return false가 되는 시점이 있을 것이다. 그 때 return true가 반환되면서 result +=1 이 되는 것이다!
잘 모르겠으면 꼭 한번 쭉 Flow를 그려보기를 추천합니당 ㅎㅎ
3. 미로 탈출
문제
동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.
입력
- 첫째 줄에 두 정수 N, M(4 <= N, M <= 200)이 주어진다. 다음 N개의 줄에는 각각 M개의 정수(0 혹은 1)로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.
출력
- 첫째 줄에 최소 이동 칸의 개수를 출력한다.
입력예시
5 6
101010
111111
000001
111111
111111출력예시
10리뷰 및 풀이
이 문제는 내가 왜 DFS를 써야겠다고 생각한지 모르겠는데 DFS를 쓰다가 혼돈에 빠져 문제를 풀지 못했다... 하지만 DFS를 썼어도 풀 수 있지 않았을까...? 아직은 DFS와 BFS에 대해 감을 잘 못잡은 것 같다..
- 이 문제는 BFS를 사용할 때 효과적으로 해결할 수 있다. BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색하기 때문이다. (BFS를 수행하면서 모든 노드의 값을 거리 정보로 넣는다)
- 즉, 특정한 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 리스트에 저장한다.
# DFS와 BFS PART2 실전문제) 미로탈출
from collections import deque
N, M = map(int, input().split())
maze = [list(map(int, input())) for _ in range(N)]
# 상하좌우 이동 방향 정의
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque() # BFS를 위해 Queue 선언
queue.append((x, y))
while queue:
x, y = queue.popleft()
# 현재 위치에서 상하좌우 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어난 경우
if nx < 0 or ny < 0 or nx >= N or ny >= M:
continue
# 위치가 벽일 경우
if maze[nx][ny] == 0:
continue
# 이동이 가능한 경우
if maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1 # 이전 값을 더해준다
queue.append((nx, ny))
return maze[N-1][M-1] # 맨 오른쪽 아래의 값을 출력해준다
print(bfs(0, 0))이 문제는 BFS로 써야겠다는 판단을 하고 BFS의 전반적인 사용 방법(deque)에 대해서 알았다면 어렵지 않게 해결을 했을 수도 있을 것 같다는 생각을 했다..!
조금 더 많이 풀어보면서 감을 빨리 익혀야겠다.
Reference
