[백준] 4991번 : 로봇 청소기

https://www.acmicpc.net/problem/4991

4991번: 로봇 청소기

해당문제는 다이나믹프로그래밍, 비트마스킹, 완전탐색, 깊이우선탐색, 너비우선탐색을 활용하여 문제를 해결 하였습니다.

너비우선탐색으로는 0과 *, *과* 사이의 거리를 구하였고, dp 테이블에 각각의 사이를 메모리제이션 하였습니다.

완전탐색과 깊이우선탐색, 비트마스킹으로 모든 경우의수를 방문 합니다.

 

from sys import stdin
from collections import deque
input = stdin.readline
move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
INF = int(10e9)


def dfs(startidx, visited, cost):
    if cost > minvalue:
        return INF

    if visited == (1 << len(dirtylist)) - 1:  # 모든 곳을 방문했다면
        return cost
 
    min_cost = INF
    for endidx in range(len(dirtylist)):
        if not visited & (1 << endidx):
            new_visited = visited | (1 << endidx)
            new_cost = cost + bfs(startidx, endidx)
            min_cost = min(min_cost, dfs(endidx, new_visited, new_cost))

    return min_cost


def bfs(startidx, endidx):  # start 부터 end 까지 최소거리 탐색 , 만약 가지 못한다면 INF
    if dp[startidx][endidx] != None:
        return dp[startidx][endidx]
    
    visited = [[False for _ in range(w)] for _ in range(h)]
    queue = deque()
    y, x = dirtylist[startidx]
    end_y, end_x = dirtylist[endidx]
    queue.append([y, x, 0])
    while queue:
        i, j, cost = queue.popleft()
        for dy, dx in move:
            ny = dy + i
            nx = dx + j
            if h > ny >= 0 and w > nx >= 0 and not visited[ny][nx] and not graph[ny][nx] == 'x':
                visited[ny][nx] = True
                if ny == end_y and nx == end_x:
                    dp[startidx][endidx] = cost + 1
                    return dp[startidx][endidx]

                queue.append([ny, nx, cost + 1])

    dp[startidx][endidx] = INF
    return dp[startidx][endidx]


while True:
    w, h = map(int, input().split())  # 너비, 높이
    if w == 0 and h == 0:  # 0,0이 주어지면 종료한다.
        break
    else:
        graph = []
        dirtylist = []
        
        start = 0
        for i in range(h):
            char = list(map(str, input()))
            for j in range(len(char)):
                if char[j] == '*' or char[j] == 'o':
                    dirtylist.append([i, j])
                if char[j] == 'o':
                    start = len(dirtylist) - 1
            graph.append(char)
            
        minvalue = INF
       
        dp = [[None for _ in range(len(dirtylist))] for _ in range(len(dirtylist))]
        for endidx in range(len(dirtylist)):
            visited = 1 << start
            if not visited & (1 << endidx):
                visited |= 1 << endidx
                minvalue = min(minvalue, dfs(endidx, visited, bfs(start, endidx)))

        if minvalue != INF:
            print(minvalue)
        else:
            print(-1)