백준 4991번 파이썬 문제풀이

문제

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

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

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

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

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

입력

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

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

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

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

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

출력

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

문제풀이 

이 문제는 전체 쓰레기를 치우는 최소 시간을 찾는 문제다. 최단거리로 문제로 치환할 수 있기 때문에 BFS와 연관된 느낌이 진하게 온다. BFS는 방문 처리 배열로 무한반복을 막아주어야 하는데, 그렇다면 이 문제에서 방문 배열은 어떻게 작성을 해야할까? 

예제의 7 5를 한번 보자. 청소기 아래에 있는 쓰레기를 가장 처음 치웠을 때, 그리고 청소기 오른쪽에 있는 쓰레기를 가장 처음 치웠을 때 걸리는 최소 시간이 달라진다는 것을 알 수 있다. 그렇다면 어떤 쓰레기를 먼저 치우느냐에 의존적인지, 아니면 치운 쓰레기 갯수에 의존적인지를 살펴보자. 

7,5에서도 알 수 있고, 15,13에서는 더욱 명확해진다. 결론부터 말하면 '어떤 쓰레기를 먼저 치우느냐에 따라 최소 시간이 의존적'이라는 것이다. 예제 15,13은 사분면으로 치워야 할 쓰레기가 나누어져있다. 각각 쓰레기를 하나씩 치운 후에 다시 중앙으로 모이게 될 것이다. 

만약 치운 갯수 별로 경우를 나누었다고 하면, 중간에서 최소 시간들이 만나기 때문에 기존에 가지고 있는 로직으로는 더 이상 탐색이 어려운 것을 알 수 있다. 즉, 내가 치운 쓰레기들을 기록하면서, 그 기록에 대한 값을 가지고 그래프 탐색을 꾸준히 해야한다.

그렇다면 각 경우의 수에 대해 방문 배열을 전부 만들어서 공간상 문제가 없는지 살펴보자. 최악의 경우를 살펴보면 (20 * 20 * 512 * 4) // (1024 * 1024) = 0.78MB로 메모리 제한과는 거의 무관한 것을 알 수 있다. 즉, 이번 문제는 비트마스킹을 통해 각 경우의 수에 대한 방문 처리를 하면서, 최소 경로를 확인하는 문제로 정리할 수 있다.

 

BFS는 아래 논리로 진행한다.

1. 큐에서 값을 하나 뺀다. 만약 쓰레기를 치운 cnt와 전체 쓰레기 카운트가 같으면 종료.
2. 다음 탐색할 범위에 대해 아래를 수행한다.
   2-1. 만약 o나 .일 경우, 현재 쓰레기를 치운 상태에서 기록된 값이 현재 시간 + 1 보다 작다면 추가적으로 그래프 탐색을 한다
   2-2. 쓰레기를 만난 경우
       2-2-1. 내가 가지고 있지 않은 쓰레기면, 치운 쓰레기 상태를 업데이트 해준다. 업데이트 한 쓰레기 상태를 기준으로 방문 배열에 time + 1을 처리해준다.
       2-2-2. 내가 가지고 있는 쓰레기면, 현재 쓰레기 상태에서 방문할 지점에 기록된 시간이 현재 시간 + 1보다 크다면 그래프 탐색을 계속한다. 이유는 아래에 후술.

***
x.x
*..

2-2-2의 케이스를 반드시 고려해주어야 하는 경우는 위 케이스가 있기 때문이다. 즉, 1행의 가운데 별을 치우고, 1행의 왼쪽별을 치우게 된다. 왼쪽별을 치우고 다시 다른 별을 치우러 가운데 별로 나와야 하는데, 이 때 청소한 상태에는 가운데 별을 처음 만나지 않았다. 그렇지만 계속 탐색을 해야한다는 것을 알 수 있다. 

그렇다면 어떻게 케이스를 정리해주어야 할까? 바로 현재 쓰레기 상태에서 방문할 지점에 기록된 시간이 현재 시간 + 1보다 클 때에만 그래프 탐색을 계속하는 것이다. 만약 그것보다 시간이 작다면, 이미 이 지점은 예전에 탐색을 했던 이력이 있기 때문에 또 탐색해봐야 했던 일을 반복하게 되는 것일 뿐이다. 

 

위의 내용을 고려하면, 코드는 아래와 같이 작성할 수 있다.

import sys
from collections import deque


# 탐색 함수
# 시작 지점 확보
# 쓰레기 위치를 기준으로 비트마스킹 사용
def find_start(vv, my_map,n,m) :
    for i in range(n) :
        for j in range(m) :
            if my_map[i][j] == 'o' :
                start = (i,j)
            elif my_map[i][j] == '*' :
                vv.append((i,j))

    return start

# BFS 함수
def bfs(n,m,my_map) :

    #변수 초기화
    que = deque()
    answer = 9876543210
    vv = []
    start = find_start(vv, my_map,n , m)

    #방문 배열 초기화
    # 2**(len(vv)) + 1 경우의 수만큼 3차원 배열을 만듦 (비트마스킹)
    v = [[[9876543210 for _ in range(m)] for _ in range(n)] for _ in range(2**(len(vv)) + 1 )]

    #전체 쓰레기 갯수, 종료 조건
    d_cnt = len(vv)
    que.append((start[0], start[1], 0, 0, 0  ))


    while que :
        r, c, cnt, time, dirty_status = que.popleft()
        if cnt == d_cnt :
            answer = min(time,answer)

        for rr,cc in tra_list :
            next_r = r + rr
            next_c = c + cc
            if -1 < next_r < n and -1 < next_c < m :


                #일반 통로나 로봇 청소기 시작 지점을 만남
                #현재 쓰레기 상태에서 이전에 방문했는지 확인 후, 방문하지 않으면 추가 탐색한다.
                if my_map[next_r][next_c] =='.' or my_map[next_r][next_c] =='o' :
                        if v[dirty_status][next_r][next_c] > time + 1 :
                            v[dirty_status][next_r][next_c] = time + 1
                            que.append((next_r, next_c, cnt, time + 1, dirty_status ))

                #쓰레기를 만남.
                #처음 만난 쓰레기라면, 쓰레기 상태를 업데이트 해준 후, 업데이트 한 쓰레기 상태의 방문 노드에 방문 처리 해준다.
                elif my_map[next_r][next_c] == '*' :
                    if dirty_status & 2 ** vv.index((next_r,next_c)) == 0 :
                        next_dirty_status = dirty_status | 2 ** vv.index((next_r,next_c))
                        v[next_dirty_status][next_r][next_c] = time + 1
                        que.append((next_r, next_c, cnt + 1 , time + 1 , next_dirty_status))
                
                #내가 이미 치웠던 쓰레기라면, 현재 쓰레기 상태로 여기를 온 적이 있는지 확인. 
                #일전에 이 상태로 온 적디 없다면, 현재 쓰레기 상태에서 방문 처리 한 후 추가 탐색한다.
                    
                    else :
                        if v[dirty_status][next_r][next_c] > time + 1 :
                            v[dirty_status][next_r][next_c] = time + 1
                            que.append((next_r, next_c, cnt, time + 1, dirty_status))

    #answer가 초기값 그대로면 -1
    if answer == 9876543210 :
        print(-1)
        return
    else :
        print(answer)
        return






tra_list = [[1,0],[0,1],[-1,0],[0,-1]]
while 1 :

    # 변수 입력 받기
    m,n = map(int,sys.stdin.readline().split())
    if m == 0 and n == 0  :
        break
    else :
        my_map = []
        for _ in range(n) :
            my_map.append(str(sys.stdin.readline().rstrip()))


        bfs(n,m,my_map)