[BOJ] 4991 - 로봇 청소기 (Python)

 

 

아이디어

 

BFS로 탐색하며 방문한 더러운 칸의 개수에 따라 비트마스킹으로 방문 표시한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

delta = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solution():
    while 1:
        w, h = map(int, input().split())
        if w == 0:
            break
        board = [[*input().rstrip()] for _ in range(h)]
        queue = []
        total = 0
        for r in range(h):
            for c in range(w):
                if board[r][c] == '*':
                    board[r][c] = f'{1<<total}'
                    total += 1
                elif board[r][c] == 'o':
                    board[r][c] = '.'
                    queue.append((r, c, 0, 0))
        if total == 0:
            print(0)
            continue
        visited = [[[0]*(1<<total) for _ in range(w)] for _ in range(h)]
        visited[queue[0][0]][queue[0][1]][0] = 1
        while queue:
            r, c, b, cnt = queue.pop(0)
            if b == (1<<total)-1:
                print(cnt)
                break
            for dr, dc in delta:
                nr, nc = r+dr, c+dc
                if h > nr >= 0 and w > nc >= 0:
                    if visited[nr][nc][b] == 0:
                        if board[nr][nc].isdigit():
                            _b = int(board[nr][nc])|b
                            visited[nr][nc][b] = 1
                            visited[nr][nc][_b] = 1
                            queue.append((nr, nc, _b, cnt+1))
                        elif board[nr][nc] == '.':
                            visited[nr][nc][b] = 1
                            queue.append((nr, nc, b, cnt+1))
        else:
            print(-1)

solution()