BFS) 4991.로봇 청소기

solution

중복되는 탐색 루트 제거. 시간 복잡도 10! x 10 = 36288000 = 약 3천만

문제의 관건은 중복되는 탐색 루트를 줄이는 것이다.
문제 유형은 브루트 포스 + BFS인데, 더러운 곳의 개수가 10개 미만이고, 격자 칸의 최대 크기는 20*20이므로, 만일 10개의 더러운 칸으로 만드는 순열의 조합 각각의 경우 BFS 탐색을 한다고 하면, 최악의 경우 시간 복잡도 10! x 20*20  >= 12억이다.
따라서 중복되는 탐색 루트를 제거할 필요가 있다.
시작점에서부터 더러운 곳을 차례로 방문하는 경우의 최단 거리는 중복된다.
가령, 더러운 곳이 3 곳이고, 그 번호를 1,2,3으로 하며, 더러운 곳과 시작점을 모두 정점이라고 한다면, 모든 순열의 경우의 수는
시작점 -> 1 -> 2 -> 3 
시작점 -> 1 -> 3 -> 2
시작점 -> 2 -> 1 -> 3
시작점 -> 2 -> 3 -> 1 
시작점 -> 3 -> 1 -> 2
시작점 -> 3 -> 2 -> 1
인데, 여기서 시작점 -> 1, 1 -> 2, 2 -> 3 과 같은 루트들이 중복된다.
따라서 초기 BFS 탐색 한 번으로 정점 간의 최단 거리를 배열 d에 저장하면, 각 순열의 경우의 수에서 정점 간에 최단 거리를 구하기 위해 매번 BFS를 수행하지 않아도 된다.

from collections import deque
from itertools import permutations
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def bfs(a, sx, sy):
    n = len(a)
    m = len(a[0])
    dist = [[-1]*m for _ in range(n)]
    q = deque()
    q.append((sx,sy))
    dist[sx][sy] = 0
    while q:
        x,y = q.popleft()
        for k in range(4):
            nx,ny = x+dx[k], y+dy[k]
            if 0 <= nx < n and 0 <= ny < m:
                if dist[nx][ny] == -1 and a[nx][ny] != 'x':
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx,ny))
    return dist

while True:
    m,n = map(int,input().split())
    if n == 0 and m == 0:
        break
    a = [input() for _ in range(n)]
    b=[(0,0)] # 더러운 곳과 시작점을 모두 정점으로 갖는 배열
    for i in range(n):
        for j in range(m):
            if a[i][j]=='o':
                b[0]=(i,j) # 시작점을 배열의 첫 번째 요소로 갖는다.
            elif a[i][j]=='*':
                b.append((i,j))
    l=len(b)
    d=[[0]*l for _ in range(l)] # 정점 간에 최단 거리를 저장한 배열
    ok=True
    for i in range(l):
        dist=bfs(a,b[i][0],b[i][1])
        for j in range(l):
            d[i][j]=dist[b[j][0]][b[j][1]]
            if d[i][j]==-1: # 만약 한 번이라도 탐색할 수 없는 경우가 나오면 -1  출력
                ok=False
                break
    if not ok:
        print(-1)
        continue
    p=[i+1 for i in range(l-1)] # 시작점은 제외
    ans=1e9
    for permu in permutations(p,len(p)): # 시작점을 제외한 정점들의 인덱스를 순열로 만든다.
        res=d[0][permu[0]]
        for i in range(l-2):
            res+=d[permu[i]][permu[i+1]]
        ans=min(ans,res)
    print(ans)