[백준] 아맞다 우산 (17244)

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

정말 친절한 문제이다.
보자마자 BFS로 접근해야겠다는 생각을 했다.
물건의 개수가 최대 5개이므로 permutation을 써야겠다는 생각을 했지만 각 순열에 따라 BFS를 진행하면 시간초과가 날 것 같아 다른 방법으로 접근했다.

미리 BFS를 돌려, 각 지점에서(Start, X, End) 모든 지점까지의 거리를 BFS로 구하여 각 2차원배열에 집어넣었다.
distance 예시

그런 다음 모든 경우의수를 담은 permutations(1, 2... X)를 구하여 모든 경우의 수의 시간을 구하고 그 중 최솟값을 출력하였다.

from collections import deque
from itertools import permutations

col, row = map(int, input().split())
graph = [list(input()) for _ in range(row)]
start_location = []
something_location = []
dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]
end_location = []

for r in range(row):
    for c in range(col):
        if graph[r][c] == 'S':
            start_location.append((r, c))
        if graph[r][c] == 'X':
            something_location.append((r, c))
        if graph[r][c] == 'E':
            end_location.append((r, c))
something_location.insert(0, start_location[0])
something_location.append(end_location[0])
distance = [[0 for _ in range(len(something_location))] for _ in range(len(something_location))]
# something_lcoations은 [S, X1, X2, ..., Xn. E]가 담겨있다.

def BFS(x, y, idx):
    q = deque()
    q.append((x, y))
    visited = [[0 for _ in range(col)] for _ in range(row)]
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for dx, dy in dir:
            nx, ny = x + dx, y + dy
            if nx < 0 or ny < 0 or nx >= row or ny >= col or graph[nx][ny] == '#' or visited[nx][ny]:
                continue
            if graph[nx][ny] == 'X' or graph[nx][ny] == 'S' or graph[nx][ny] == 'E':
                distance[idx][something_location.index((nx, ny))] = visited[x][y]
            visited[nx][ny] = visited[x][y] + 1
            q.append((nx, ny))


for idx, data in enumerate(something_location):
    BFS(data[0], data[1], idx)

result = 1e9
locations = [i + 1 for i in range(len(something_location) - 2)]
for permu in list(permutations(locations)):
    nl = [0] + list(permu) + [len(something_location) - 1]
    permu는 tuple이기에 list로 형변환 해주었다.
    temp = 0
    for idx in range(1, len(nl)):
        temp += distance[nl[idx]][nl[idx - 1]]
    result = min(result, temp)

print(result)