[백준 4991] 로봇 청소기

 

4991번: 로봇 청소기

 

로봇 청소기의 시작 위치, 더러운 칸을 정점으로 잡아 새로운 그래프를 만들어 TSP를 해결하면 되는 문제이다. 정점의 개수는 11개(로봇 청소기 위치 + 더러운 칸의 개수)이기 때문에 11!(=39,916,800)가 작아 완전탐색을 돌릴 수 있다.

 

간선은 A에서 B로 이동할 때 거리를 의미하므로 이 부분은 BFS로 미리 구해놓으면 된다.

 

아래 코드는 TSP를 계산할 때 완전탐색을 이용하였다. 이를 더 빠르게 돌아가게 하고 싶다면 TSP 관련 알고리즘을 공부하고 적용하면 된다.

 

from collections import deque
import sys
import itertools

def input():
    return sys.stdin.readline().rstrip()

def inrange(y, x, N, M):
    return 0 <= y and y < N and 0 <= x and x < M

Dy = (-1,1,0,0)
Dx = (0,0,-1,1)

while True:
    M, N = map(int,input().split())
    if N == 0 or M == 0: break
    Map = [list(input()) for _ in range(N)]
    ids = [[-1 for j in range(M)] for i in range(N)]
    points = [(0, 0)]

    for i in range(N):
        for j in range(M):
            if Map[i][j] == 'o':
                points[0] = (i, j)
                ids[i][j] = 0
            elif Map[i][j] == '*':
                ids[i][j] = len(points)
                points.append((i, j))

    dist = [[-1 for j in range(11)] for i in range(11)]

    for idx, (y, x) in enumerate(points):
        Q = deque([(y, x)])
        cur_dist = [[-1 for j in range(M)] for i in range(N)]
        cur_dist[y][x] = 0

        while Q:
            cy, cx = Q.popleft()

            for dy, dx in zip(Dy, Dx):
                ny, nx = cy + dy, cx + dx
                if not inrange(ny, nx, N, M): continue
                if cur_dist[ny][nx] != -1: continue
                if Map[ny][nx] == 'x': continue
                cur_dist[ny][nx] = cur_dist[cy][cx] + 1
                Q.append((ny, nx))

        for idx2, (y2, x2) in enumerate(points):
            if idx == idx2: dist[idx][idx2] = 0
            else: dist[idx][idx2] = cur_dist[y2][x2]

    seqs = itertools.permutations([i for i in range(1, len(points))], len(points) - 1)
    ans = 0 if len(points) == 1 else -1
    for seq in seqs:
        cur_ans = 0
        S = 0
        for nxt in seq:
            if dist[S][nxt] == -1:
                cur_ans = -1
                break
            cur_ans += dist[S][nxt]
            S = nxt

        if cur_ans == -1: continue
        if ans == -1: ans = cur_ans
        elif ans > cur_ans: ans = cur_ans

    print(ans)