문제
접근
BFS 문제이다.
따로 방문배열을 사용할 필요가 없어서 Board 하나로만 이용했다.
BFS의 가장 편한 점은 일반적인 경우에 최초 방문한 지점은 항상 최단 거리로 방문했음을 확신할 수 있다.
때문에 최초 방문만 신경써서 처리해주면, 이미 방문한 지점에 대해서는 따로 고민할 필요가 없다.
코드
- 파이썬 코드
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
27
28
29
30
31
32
33
34
from collections import deque
def bfs(q):
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = 1
while q:
nowx, nowy = q.popleft()
for x, y in zip(dx,dy):
nx = x + nowx
ny = y + nowy
if nx < 0 or nx >= w or ny < 0 or ny >= h:
continue
if board[ny][nx] == 0:
board[ny][nx] = board[nowy][nowx] + 1
q.append((nx, ny))
ans = max(ans, board[ny][nx])
for i in range(h):
for j in range(w):
if board[i][j] == 0:
return -1
return ans-1
w, h = map(int, input().split(' '))
board = []
q = deque()
for i in range(h):
board.append(list(map(int, input().split(' '))))
for j in range(w):
if board[i][j] == 1:
q.append((j,i))
print(bfs(q))