문제
N×M크기의 배열로 표현되는 미로가 있다.
1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.
출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.
예제 입력
4 6
101111
101010
101011
111011
예제 출력
15
풀이
bfs-큐 방법으로 해결하였다. bfs-큐 개념을 이용한 일반적인 문제인 것 같다.
bfs 로 탐색하면서, 유효한 좌표(값이 1)이면서 방문하지 않은 좌표인 경우 큐에 넣고, 해당 좌표값을 "직전 노드 좌표값 + 1" 로 설정해준다. 이렇게 하면 방문한 좌표임을 표시하면서 해당 좌표까지 걸린 이동 횟수까지 알 수 있다.
따라서 마지막 좌표는 시작 좌표에서부터 해당 좌표까지의 이동 횟수를 좌표값으로 가지고 있다.
기타
한가지 생각해볼 점이 있다. 북-동-남-서 순으로 bfs 탐색을 한다고 가정해보자. [0][1] 의 좌표값이 1인 경우, 앞서 말했듯 [0][1]의 값을 직전 좌표값인 [0][0]의 값(1) + 1 로 설정해주고, [0][1]을 기준으로 다시 bfs 탐색을 하면 [0][0]을 탐색하게 되고 해당 좌표값이 1이기때문에 [0][0]의 좌표값을 변경시키게 된다는 점이다.
그러나 이미 [0][0]을 제외한 유효한 좌표가 존재하는 경우 절대 문제의 답이 [0][0]의 좌표값이 될 수 없기 때문에 무시할 수 있게 된다.
from collections import deque
n, m = map(int, input().split()) # 행 개수, 열 개수
arr = [[0 for _ in range(m)] for _ in range(n)] # 배열 초기화
# 배열에 좌표값 입력
for i in range(n):
lst = list(input())
for j in range(m):
arr[i][j] = int(lst[j])
def bfs():
# 탐색 시작([0][0] 에서 출발, [n-1][m-1] 에서 멈춤)
queue = deque()
queue.append([0,0]) # 시작 노드 삽입
while queue:
v = queue.popleft()
x = v[0]
y = v[1]
# 사방으로 bfs 탐색
# 유효한 좌표 & 아직 방문안했으면 큐에 넣음 & 직전 좌표의 값 + 1
# 북
if(x > 0 and arr[x-1][y] == 1):
queue.append([x-1,y])
arr[x-1][y] = arr[x][y] + 1
# 동
if(y < m-1 and arr[x][y+1] == 1):
queue.append([x,y+1])
arr[x][y+1] = arr[x][y] + 1
# 남
if(x < n-1 and arr[x+1][y] == 1):
queue.append([x+1,y])
arr[x+1][y] = arr[x][y] + 1
# 서
if(y > 0 and arr[x][y-1] == 1):
queue.append([x,y-1])
arr[x][y-1] = arr[x][y] + 1
bfs()
print(arr[n-1][m-1])