백준 4991 로봇 청소기

최단거리를 찾는 bfs문제이다.
근데 bfs에 다른 알고리즘을 접목시켜야 연산시간을 줄일 수 있다.
더러운 칸의 위치가 10개뿐이라는 점이 눈여겨볼 지점인데,
10개 칸을 완전탐색으로 돈다면 10!로 나열할 수 있고, 이 경우를 bfs로 돌린다면 cpp에선 통과가 가능할 지 몰라도, 파이썬에선 시간초과가 났다.

다른사람들의 풀이를 참조했고 이 문제는 TSP방식과 비트마스킹을 사용할 수 있다.

비트마스킹 풀이를 썼는데, https://programmers.co.kr/learn/courses/30/lessons/81304
이 문제에서 비트마스킹을 사용한 개념을 착안하면 된다.

bfs를 돌면서, 청소해야할 위치를 0,1,2,...로 놓고 해당 위치를 방문시 해당 위치에 비트를 켜고, 모든 비트가 켜져있다면, 청소가 모두 끝난것으로 판단하면 된다.
visited배열에 bit라는 범위를 만들어 3차원 visited배열을 만들었다.

from collections import deque
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def bfs(wasted,robot):
    visited = [[[0]*(1<<10) for i in range(w)] for i in range(h)]
    queue = deque([])
    queue.append((robot[0],robot[1],0))
    while queue:
        x,y,clean_bit = queue.popleft()
        if clean_bit == (1 << len(wasted)) -1:
            return visited[x][y][clean_bit]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or ny < 0 or nx >= h or ny >= w or arr[nx][ny] == 'x': continue
            if arr[nx][ny] == '*':
                next_bit = clean_bit | (1<<wasted.index((nx,ny)))
                if not visited[nx][ny][next_bit]:
                    queue.append((nx,ny,next_bit))
                    visited[nx][ny][next_bit] = visited[x][y][clean_bit] + 1
            else:
                if not visited[nx][ny][clean_bit]:
                    queue.append((nx,ny,clean_bit))
                    visited[nx][ny][clean_bit] = visited[x][y][clean_bit] + 1
    return -1
while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0:
        break
    arr = []
    for i in range(h):
        arr.append(list(input()))
    wasted = []
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '*':
                wasted.append((i,j))
            elif arr[i][j] == 'o':
                robot = [i,j]
    print(bfs(wasted,robot))