[BOJ/백준] 4991 로봇 청소기 파이썬

문제 링크 : https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

 

비트마스킹으로 해결한 문제이다.

예전에 풀었던건데 그때는 BFS+DFS로 풀었다.

이 방법은 느리다. 모든 시작점과 더러운칸에서 BFS를 진행하고 마지막에 DFS를 진행 했기 때문이다.

그때의 알고리즘은 아래 더보기를 누르면 된다.

시작점과 더러운칸에 0부터 번호를 매기고 start라는 배열에 번호를 저장했다.

그리고 start배열의 점에서 각각 BFS를 실행하여 각 점사이의 거리 최솟값을 구해서 저장했다.

그 다음 0번 부터 시작해서 DFS를 실행하면서 거리의 합을 계산한다.

이때 모든 점을 방문했다면 거리의 최솟값을 갱신해서 답을 구했다.

 

from sys import stdin
from collections import deque

dx = [-1,1,0,0]
dy = [0,0,-1,1]
w,h = -1,-1
ans = 1000000000
def bfs(sx,sy,board,len_list):
    q = deque()
    visited = [[False]*w for _ in range(h)]

    q.appendleft((sx,sy,0))
    visited[sx][sy] = True

    while q:
        x,y,cnt = q.pop()
        if not board[x][y] in ['.', 'x'] and (x != sx or y != sy):
            point = int(board[x][y])
            len_list[point] = cnt

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if not point_validator(nx,ny,visited):
                continue
            visited[nx][ny] = True
            q.appendleft((nx,ny,cnt+1))

    return len_list

def search_ans(len_list,now,visited_cnt,cnt,visited):
    if visited_cnt == len(len_list):
        global ans
        ans = min(ans,cnt)
        return
    for nxt in range(len(len_list[now])):
        if len_list[now][nxt] == 0 or visited[nxt]:
            continue
        visited[nxt] = True
        search_ans(len_list,nxt,visited_cnt+1,cnt+len_list[now][nxt],visited)
        visited[nxt] = False

def point_validator(x,y,visited):
    if x < 0 or y < 0 or x >= h or y >= w:
        return False
    elif board[x][y] == 'x':
        return False
    elif visited[x][y]:
        return False
    return True

while True:
    w,h = map(int, stdin.readline().strip().split())
    if w==0 and h==0:
        break
    sx,sy = -1,-1
    start = []
    board = []
    point_num = 0
    for i in range(h):
        board.append(list(stdin.readline().strip()))
        for j in range(w):
            if board[i][j] == 'o':
                sx,sy = i,j
                start.append((i,j))
                board[i][j] = str(point_num)
                point_num += 1
            elif board[i][j] == '*':
                start.append((i,j))
                board[i][j] = str(point_num)
                point_num += 1

    len_list = [[] for _ in range(len(start))]
    ans = 1000000000

    start_point = int(board[sx][sy])
    for x,y in start:
        point = int(board[x][y])
        len_list[point] = bfs(x,y,board,[0]*len(start))

    visited = [False]*len(len_list)
    visited[start_point] = True
    search_ans(len_list, start_point, 1, 0, visited)
    print(ans if ans != 1000000000 else -1)

 

새로운 풀이는 그냥 비트마스킹을 이용하는 것이다.

 

더러운칸은 최대 10이므로 충분하다. 2^10은 1024이기 때문에 비트마스킹으로 충분하다.

더러운칸 마다 0부터 번호를 매겼다.

 

그리고 BFS를 진행하면서 방문한 더러운 칸의 정보를 가지고 다니자.

만약 다음칸이 더러운 칸이라면 해당 정보의 방문하려는 더러운 칸의 번호의 비트를 바꿔주면 된다.

방문체크는 3차원으로 했다. 해당 좌표에 해당 더러운 칸의 정보로 방문한 경우는 중복된것 이다.

 

마지막으로 모든 더러운 칸을 방문했는지 확인하는 것이다.

맵을 입력받을 때 더러운 칸일 경우 번호를 매긴다고 했다.

이때 target_bitmask라는 변수에 해당 번호의 비트를 1로 바꿨다.

비트가 1인 경우 해당 더러운 칸은 방문 했다는 것이므로 모든 비트가 1인 것은 모든 칸을 방문했다는 것이다.

따라서 target_bitmask와 BFS를 진행하면서 생성한 더러운 칸 정보를 비교하여 모든 칸을 방문했는지 체크할 수 있다.

 

from sys import stdin
from collections import deque

input = stdin.readline
dx = [-1,1,0,0]
dy = [0,0,-1,1]

visited = [[[0]*2**10 for _ in range(20)] for _ in range(20)]
visited_num = 0
w=h=0
def solv():
    global w,h
    while True:
        w,h = map(int, input().split())
        if w == h == 0:
            return

        board = []
        sx=sy=-1
        trash_idx = 0
        target_bitmask = 0
        for x in range(h):
            board.append(list(input().strip()))
            for y in range(w):
                if board[x][y] == 'o':
                    sx,sy=x,y
                    board[x][y] = '.'
                elif board[x][y] == '*':
                    target_bitmask |= (1<<trash_idx)
                    board[x][y] = str(trash_idx)
                    trash_idx += 1

        print(bfs(sx,sy,board,target_bitmask))

def bfs(sx,sy,board,target_bitmask):
    global visited,visited_num
    visited_num += 1
    visited[sx][sy][0] = True

    q = deque([(sx,sy,0,0)])

    while q:
        x,y,cnt,bitmask = q.pop()
        if bitmask == target_bitmask:
            return cnt

        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if boundray_validator(nx,ny,board):
                if board[nx][ny].isdigit():
                    trash_idx = int(board[nx][ny])
                    nxt_bitmask = bitmask | (1<<trash_idx)
                    if visited[nx][ny][nxt_bitmask] != visited_num:
                        visited[nx][ny][nxt_bitmask] = visited_num
                        q.appendleft((nx,ny,cnt+1,nxt_bitmask))
                else:
                    if visited[nx][ny][bitmask] != visited_num:
                        visited[nx][ny][bitmask] = visited_num
                        q.appendleft((nx,ny,cnt+1,bitmask))

    return -1

def boundray_validator(x,y,board):
    if x < 0 or y < 0 or x >= h or y >= w:
        return False
    elif board[x][y] == 'x':
        return False
    return True

solv()