BOJ - 5558 - チーズ

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):
        maps.append(list(map(str, sys.stdin.readline().strip())))
    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