[BOJ] 4991. 로봇 청소기 (🥇, BFS/비트마스킹)

🔗

풀이

✅ 문제 설명

o 에서 시작하여 가능한 모든 * 위치에 방문할 수 있는 전체 이동 거리의 최소 값을 찾는 문제이다. 만약 모든 * 에 도달할 수 없는 상황이라면 -1 을 반환한다.

💡 아이디어

시작 지점은 하나이지만 도착 지점은 여러개인 그래프 탐색 문제이다. 최소 값을 구해야 하므로 너비 우선 탐색으로 풀이할 수 있다.

BFS + DFS

단순하게 생각해서 최대 도착 지점에 10개니까 모든 경우에 대해 완전 탐색으로도 가능하다. 시작 위치에서 출발해서 1 -> 2 -> 3 으로 순서를 정해놓고 BFS 돌리고, 1 -> 3 -> 2 로 돌려보는 방식이다. BFS 와 순열을 조합하면 되는데 파이썬에서는 시간 초과가 날 거 같았다.

비트마스킹

만약 더러운 위치가 3곳이라고 가정하면 더러운 위치는 (1) 청소가 되기 전과 (2) 청소가 된 후 2가지 상태가 존재할 것이다. 서로 다른 2가지 상태가 존재할 때 이것에 대한 정보는 bit 형태로 저장할 수 있다.

각 위치에 번호를 지정한다면 3자리의 비트값을 생성하고 그림의 왼쪽과 같이 만들어줄 수 있다. 0은 청소 전, 1을 청소 후를 나타낸다고 가정하자. 000은 모든 곳을 청소하지 않았을 때, 001은 1번 위치만을 청소했을 때를 나타낸다.

시작 지점에서는 000의 값을 갖고 탐색을 시작하게 된다. 그러다 1번 위치를 찾게 되면 청소를 하고 000의 값에 1번 위치의 값을 1로 변경해야 한다. 비트마스킹 알고리즘을 통해 변경하면 다음과 같다.

bitmask | (1 << 0)

갖고 있는 전체 비트 값이 bitmask 이다. 10진수로는 0, 2진수로는 000인 값이 저장된다. 1 << 0 은 1을 한 칸씩 왼쪽으로 옮겨주게 된다. 2 ** 0 과 동일하며 001의 값을 가진다. OR 연산자를 통해서 001의 값을 bitmask 값에 합쳐주게 된다. 이제 bitmask 는 001의 값을 갖게 되며 이는 1번 위치를 청소했다는 의미를 가진다.

1번 위치를 청소했다면 이제 2,3번 위치를 청소해야 한다. 그러기 위해서는 다른 곳으로 이동해야 하는데 그래프 탐색에서 같은 위치를 재방문하기 위해서는 방문처리가 되어 있지 않아야 한다. 그렇지 않으면 여러 번 같은 곳을 재방문할 수 있기 때문이다. 1번 위치를 방문하기 전에 1번 위치에 오기 위해서 거쳤던 길은 1번 위치를 방문한 후 2,3번 위치를 방문하기 위해 이동할 때는 다시 방문할 수 있어야 한다는 뜻이다. 그러기 위해서는 1번 위치 방문 전후로 달라진 값을 기준으로 방문처리를 해야 한다. 해당 위치의 x, y 좌표값은 1번 위치를 방문하나 안 하나 항상 똑같기 때문에 2차원 visited 배열로는 이 문제를 해결할 수 없다.

1번 위치 방문 전후 달라진 값은 bitmask 의 값이 변경되었다는 것이다. 원래 0이었으나 1번을 방문하면서 1(10진수 기준)로 변경되었다. 즉, bitmask 값을 기준으로 방문처리를 하면 된다. 해당 위치가 3곳이기 때문에 bitmask 는 3자리를 갖게 되므로 2**3 만큼의 길이를 갖는 배열을 만들어 2차원 visited 배열의 모든 칸에 대입한다. 이렇게 되면 3차원 visited 배열이 되고 이제 겹치지 않게 방문처리를 할 수 있다.

❌ 실패한 풀이

2차원 형태의 visited 배열

2차원 형태로 방문처리를 해서 이미 방문한 곳을 다시 방문하거나, 방문했던 곳을 재방문하지 못해서 꼬이는 상황들이 발생했다. 처음에는 단순하게 bitmask 값을 그대로 2차원 visited 배열에 저장했는데 이렇게 되자 1번 위치만 방문했다가 오는 곳과 1번, 3번을 방문하고 오는 곳, 2번 위치만 방문하고 오는 곳 이 모든 정보들에 서로 뒤섞이면서 제대로 방문 처리가 되지 않았다.

또 큐를 돌면서 visited 배열에 저장된 값을 꺼내 사용했는데 이 값들이 BFS가 도는 과정에서 계속해서 변하는 바람에 제대로 된 값이 구해지지 않았다.

bitmask 값을 중간에 변경

큐에서 꺼낸 x, y 좌표를 기준으로 4방향 탐색을 하는 과정에서 bitmask 값을 직접적으로 변경했다. 왼쪽 방향을 탐색하면서 bitmask 값이 변경되자 변경된 값으로 오른쪽, 위쪽, 아래쪽을 탐색했고 결국 계속 잘못된 값이 계산되고 있었다.

그 외

그 외에도 초기에 코드 작성할 때는 출발점도 비트 값에 포함을 시켰다가 나중에 변경했는데 변경한 걸 까먹고 visited 배열의 출발점 위치에 1<<0 값에 True를 주는 바람에 틀렸었다... 출발 위치는 visited[출발위치][0] 번에 줘야 하는데 1<<0은 1이기 때문이다.

# 로봇 청소기 

import sys
input = sys.stdin.readline

def find_start(arr):
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == 'o':
                return i, j

def find_dirty(arr):
    dirty = {}
    cnt = 0
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            if arr[i][j] == '*':
                dirty[(i, j)] = cnt
                cnt += 1
    return dirty

def bfs(arr, start, dirty):
    visited = [[[False] * (1 << len(dirty)) for _ in range(w)] for _ in range(h)]
    queue = [(*start, 0, 0)]
    target_bitmask = (1 << len(dirty)) - 1
    while queue:
        x, y, cnt, bitmask = queue.pop(0)
        if bitmask == target_bitmask:
            return cnt
        
        for nx, ny in (x-1, y), (x+1, y), (x, y-1), (x, y+1):
            if nx < 0 or ny < 0 or nx >= h or ny >= w or arr[nx][ny] == 'x':
                continue

            if arr[nx][ny] == '*':
                next_bitmask = bitmask | (1 << dirty[(nx, ny)])
                if not visited[nx][ny][next_bitmask]:
                    visited[nx][ny][next_bitmask] = True
                    queue.append((nx, ny, cnt+1, next_bitmask))
            elif not visited[nx][ny][bitmask]:
                visited[nx][ny][bitmask] = True
                queue.append((nx, ny, cnt+1, bitmask))

    return -1

while True:
    w, h = map(int, input().split())
    if (w, h) == (0, 0):
        break

    ROOM = [list(input()) for _ in range(h)]
    dirty = find_dirty(ROOM)
    print(bfs(ROOM, find_start(ROOM), dirty))