백준 알고리즘 5558번 チーズ(python)

S에서 시작해서 1부터 N까지 순서대로 들렀을 때의 최단거리를 구해야 되는 BFS 문제이다.

1에 들러야 된다고 해서 2를 지나가면 안 된다는 것은 아니다. 

목적지(1, 2, ... N)에 도착할 때마다 시작점부터 이동한 거리를 res에 더하고,

시작점과 목적지를 업데이트, 맵을 초기화하는 방식으로 해결했다.

EX) 시작점 S에서 목적지 1에 도착 -> res += 거리, 시작점 1, 목적지 2, 맵 초기화 

from collections import deque
from copy import deepcopy

def clear(target):
    for i in range(H):
        for j in range(W):
            if graph[i][j] == 'X':
                t[i][j] = -2
            else:
                t[i][j] = -1

def bfs(y, x, target):
    q = deque()
    q.append((y, x))
    clear(target)
    t[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < H) and (0 <= X < W) and t[Y][X] == -1:
                if graph[Y][X] == target: 
                    return t[y][x] + 1, Y, X
                else:
                    t[Y][X] = t[y][x] + 1
                    q.append((Y, X))
        
H, W, N = map(int, input().split())
graph = [list(input()) for _ in range(H)]
t = deepcopy(graph)
d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
res = 0
for i in range(H):
    for j in range(W):
        if graph[i][j] == 'S':
            y, x = i, j
            for n in range(1, N+1):
                z, y, x = bfs(y, x, str(n))
                res += z 
print(res)