문제
접근
단순한 2차원 BFS 문제이다.
2차원에서 상하좌우 한칸씩 이동하며 목적지까지 몇 번만에 도달했는지 확인하면 된다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from collections import deque
def bfs():
q = deque()
q.append((0,0))
visit[0][0] = 1
while q:
nowx, nowy = q.popleft()
for x, y in zip(dx, dy):
nx = nowx+x
ny = nowy+y
if nx < 0 or nx >= m or ny < 0 or ny >= n:
continue
if board[ny][nx] == 1 and visit[ny][nx] == 0:
visit[ny][nx] = visit[nowy][nowx] + 1
q.append((nx, ny))
dx = [0,0,1,-1]
dy = [1,-1,0,0]
n, m = map(int, input().split(' '))
board = []
visit = [[0] * (m) for _ in range(n)]
for i in range(n):
board.append([int(item) for item in input()])
bfs()
print(visit[n-1][m-1])