[BOJ 4991] 로봇 청소기 - Python 풀이

문제

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.

• .: 깨끗한 칸
• *: 더러운 칸
• x: 가구
• o: 로봇 청소기의 시작 위치

더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

코드 

from itertools import permutations
import sys
from collections import deque

def bfs(w, h, room, positions):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    q = deque()
    distance = [[0]  * w for _ in range(h)]
    q.append((positions[0], positions[1]))
    distance[positions[0]][positions[1]] = 1
    
    while q:
        x, y = q. popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w:
                if room[nx][ny] != "x" and not distance[nx][ny]:
                    distance[nx][ny] =  distance[x][y]+1
                    q.append((nx, ny))

    return distance

def get_minimum_clean_moves(w, h, room, dirty_count, robot_position, dirty_positions):
    distance = bfs(w, h, room, robot_position)

    robot_to_dirty = []

    for i, j in dirty_positions:
        if not distance[i][j]: 
            return -1
        robot_to_dirty.append(distance[i][j]-1)

    dirty_to_dirty = [[0]*dirty_count for _ in range(dirty_count)]
    
    for i in range(dirty_count-1):
        distance = bfs(w, h, room, (dirty_positions[i][0], dirty_positions[i][1]))
        for j in range(i+1, dirty_count):
            dirty_to_dirty[i][j] = distance[dirty_positions[j][0]][dirty_positions[j][1]]-1
            dirty_to_dirty[j][i] = dirty_to_dirty[i][j]

    permu = list(permutations([i for i in range(len(dirty_to_dirty))]))    
    minimum = sys.maxsize

    for i in permu:
        dist = 0
        dist += robot_to_dirty[i[0]]
        nfrom = i[0]
        for j in range(1, len(i)):
            nto = i[j]
            dist += dirty_to_dirty[nfrom][nto]
            nfrom = nto
        minimum = min(minimum, dist)
    
    return minimum

if __name__ == "__main__":
    while True:
        w, h = map(int, sys.stdin.readline().split())

        if not w and not h : break

        room = [["." for _ in range(w)] for _ in range(h)]
        dirty_count = 0
        robot_position = ()
        dirty_positions = []

        for i in range(h):
            input = list(sys.stdin.readline())
            for j in range(w):
                if input[j] == "x":
                    room[i][j] = "x"
                elif input[j] == "*":
                    room[i][j] = "*"
                    dirty_positions.append((i,j))
                    dirty_count += 1
                elif input[j] == "o":
                    robot_position = (i,j)

        print(get_minimum_clean_moves(w, h, room, dirty_count, robot_position, dirty_positions))

결과

풀이

먼저 문제를 보고 풀다가 모르겠어서 이 링크의 코드를 보고 풀었다. 다른 사람들의 풀이도 봤지만 가장 납득이 되는 풀이였기 때문이었다.

 

로직은 간단하다. 

o의 위치를 robot_position에 저장하고 * 들을 dirty_positions에 저장한다.

robot_position으로부터 모든 dirty_postions에 대한 거리를 구하여 robot_to_dirty에 저장한다.

모든 dirty_positions 간의 거리를 구하여 dirty_to_dirty에 저장한다.

permutations를 이용한 순열을 구하여 갈 수 있는 모든 경로를 구해놓고 거리를 다 더해본 후 최소값을 출력한다.

 

로직은 간단한데 구현하느라 어려웠다. 특히 저 순열을 사용하는 부분이 어려웠다.