🔎 문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제
풀이1. 미로의 범위를 나누어 푸는 정석적인 방법
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())
maze = [list(map(int, input().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y):
queue = deque() # 큐 생성
queue.append((x, y)) # 큐에 시작좌표 넣기
while queue: # 큐가 빌 때 까지 반복
x, y = queue.popleft() # 큐의 첫번째원소를 꺼내서 x, y에 지정
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
# 미로의 범위를 벗어나는 경우
if next_x < 0 or next_y < 0 or next_x >= n or next_y >= m:
continue # 무시
# 벽을 만난 경우(1:통로/ 0:벽)
if maze[next_x][next_y] == 0:
continue # 무시
# 이동 가능한 통로이며 아직 방문하지 않은 노드인 경우
if maze[next_x][next_y] == 1:
maze[next_x][next_y] = maze[x][y] + 1 # 직전 노드까지의 최단거리 + 1 = 현재 노드까지의 최단거리
queue.append((next_x, next_y)) # 큐에 현재 노드의 좌표 추가
return maze[n-1][m-1] # 인덱스가 [0][0]부터 시작하므로 최종 반환값은 인덱스 [n-1][m-1]
# 결과 출력
print(bfs(0,0))4 6
101111
101010
101011
111011
15
풀이2. 간단하게 작성하는 방법
import sys
from collections import deque
input = sys.stdin.readline()
n, m = map(int, input().split())
maze = [list(map(int, input().rstrip())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def dfs(x, y):
queue = deque()
queue.append((x, y))
whlie queue:
x, y = queue.popleft()
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
if 0 <= next_x < n and 0 <= next_y < m and maze[next_x][next_y] == 1:
maze[next_x][next_y] = maze[x][y] + 1
queue.append((next_x, next_y))
return maze[n-1][m-1]
print(bfs(0, 0))4 6
101111
101010
101011
111011
15
✅ 정리
Q. 이 문제에서 DFS가 아니라 BFS를 써야만 했던 이유는?
A. BFS는 최단거리/최소횟수를 구하는 경우에 사용하기 적합한 해결법이다.
| DFS(깊이 우선 탐색) | BFS(너비 우선 탐색) |
|---|---|
| 재귀함수와 백트래킹을 이용하여, 모든 경우를 하나씩 전부 탐색하는 경우 | 최단거리/최소횟수를 구하는 경우 |
| 최적의 답을 찾는 것이 아닌 경우 | 최적의 답을 찾는 경우 (BFS는 가장 처음 발견되는 답이 최단거리이다.) |
| 경로의 특징을 저장해야 하는 경우 (ex. 경로의 가중치, 이동 과정에서의 제약 등) | 탐색의 횟수를 구해야 하는 경우 |
| 그래프의 크기가 클 경우 |
Q. input = sys.stdin.readline을 넣어주는 이유는?
A. 반복문을 통해서 input()으로 여러 줄을 입력받을 때 시간초과가 발생할 수 있는데, 이를 해결할 수 있는 함수. 한줄에 여러개의 입력값을 받을 수 있으며, 함수를 사용하기 위해서는 import sys가 필요하다.
기본적으로 .readline()은 개행문자(\n)을 포함하고 있기 때문에, 이를 제거하고 공백없이 출력할 수 있게 해주는 함수들이 있다.
.rstrip(): 오른쪽 공백을 제거.lstrip(): 왼쪽 공백을 제거.strip(): 양쪽(왼쪽, 오른쪽) 공백을 제거
🔗 references
