BOJ (로봇청소기) 4991

작성일 | In

로봇청소기

  • 직사각형 모양의 방이 주어졌을 때
  • 모든 더러운 칸을 깨끗한 칸으로 바꾸기 위해 필요한 최소 이동 횟수를 구하는 문제
  • 너비, 높이 <=20, 더러운 칸의 개수 <=10
  • 가중치가 일이다.
  • 이 문제에서는 더러운 칸을 어떤 순서로 청소하냐에 따라서 필요한 최소 이동 횟수가 달라진다.
  • 더러운 칸은 10개 이하다.
  • 즉 모든 방법을 만든 다음에, 거리를 구하면 된다.
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
def next_permutation(a):
    i = len(a)-1
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a)-1
    while a[j] <= a[i-1]:
        j -= 1

    a[i-1],a[j] = a[j],a[i-1]

    j = len(a)-1
    while i < j:
        a[i],a[j] = a[j],a[i]
        i += 1
        j -= 1

    return True

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:
                ok = False
    if not ok:
        print(-1)
        continue
    p = [i+1 for i in range(l-1)]
    ans = -1
    while True:
        now = d[0][p[0]]
        for i in range(l-2):
            now += d[p[i]][p[i+1]]
        if ans == -1 or ans > now:
            ans = now
        if not next_permutation(p):
            break
    print(ans)

참고자료 codeplus

0%