# BOJ - 5558 - チーズ

Updated:

``````import sys
from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def clearArray(visit, H, W):
for i in range(H):
for j in range(W):
visit[i][j] = False

def BFS(maps, sx, sy, H, W, N):
dq = deque()
dq.append((sx, sy))
visit = [[False for _ in range(W)] for _ in range(H)]
visit[sx][sy] = True

idx = 1
step = 0

while True:
for _ in range(len(dq)):
x, y = dq.popleft()
if maps[x][y] == 'S' or maps[x][y] == '.':
pass
elif int(maps[x][y]) == idx:
if idx == N:
print(step - N + 1)
return
else:
idx += 1
dq.clear()
dq.append((x, y))
clearArray(visit, H, W)
break

for k in range(4):
nx, ny = x + dx[k], y + dy[k]
if 0 <= nx < H and 0 <= ny < W:
if maps[nx][ny] != 'X':
if visit[nx][ny] == False:
visit[nx][ny] = True
dq.append((nx, ny))
step += 1

def solution():
H, W, N = map(int, sys.stdin.readline().split())
maps = []
for _ in range(H):
sx, sy = 0, 0
for i in range(H):
for j in range(W):
if maps[i][j] == 'S':
sx, sy = i, j

BFS(maps, sx, sy, H, W, N)

solution()
``````

https://www.acmicpc.net/problem/5558

Categories:

Updated: