백준 - 4991 로봇 청소기 (그래프, BFS, 비트마스킹, 골1)

풀러가기

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.
더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.

이 문제에서 가장 중요한 부분은 더러운 칸의 개수이다. 최대 10개의 더러운 칸이기 때문에, 가장 먼저 했던 생각은 총 경우의 수를 따져보는 것이었다. 각 더러운 칸을 방문하는 경우의 수는 10! = 약 360만 정도 된다.
그래서 각 더러운 칸끼리의 최단 거리를 먼저 모두 구해 놓은 다음 완전 탐색을 해야 겠다 생각했다.

그리고 또한 생각해보니 외판원 문제와 형식이 똑같았다. 다른 점은 지난온 길을 다시 갈 수 있다는 점이었다. 그래서 여기서 생각한 것은 최대 더러운 칸의 개수가 10개이기 때문에 충분히 비트마스킹을 적용할 수 있을 것 같았고, 더러운 칸을 방문했는지 알려면 비트마스킹 기법을 사용해야 할 것 같았다.

그래서 BFS + 비트마스킹 기법을 사용했다. BFS에서 가장 중요한 것은 무한루프에 빠지지 않기 위해서 큐에 모든 값들을 담으면 안되는 것이다.

코드를 보면 다음 같다.

import sys
from collections import deque

dx = [1,-1,0,0]
dy = [0,0,1,-1]

while True:
    W, H = map(int, sys.stdin.readline().strip().split(' '))
    if W == 0 and H == 0:
        break

    MAPS = []
    dirty = []
    curX, curY = None, None
    dq = deque()
    dirty = {}
    check = [[[sys.maxsize for _ in range(1025)] for _ in range(W)] for _ in range(H)]
    for _ in range(H):
        MAPS.append(list(sys.stdin.readline().strip()))

    count = 0
    for i in range(H):
        for j in range(W):
            if MAPS[i][j] == 'o':
                curX, curY = i, j

            if MAPS[i][j] == '*':
                dirty[(i,j)] = count
                count += 1

    dq.append((curX,curY,0,0))
    ret = sys.maxsize

    while dq:
        x, y, cost , visited = dq.popleft()

        if visited == (1 << count) - 1:
            ret = min(ret, cost)

        if check[x][y][visited] < cost:
            continue

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

            if 0 <= nx < H and 0 <= ny < W and MAPS[nx][ny] != 'x':

                if (nx, ny) in dirty:
                    index = dirty[(nx, ny)]
                    nextVisited = visited | (1 << index)
                    if cost + 1 < check[nx][ny][nextVisited]:
                        dq.append((nx,ny,cost+1, nextVisited))
                        check[nx][ny][nextVisited] = cost + 1
                else:
                    if cost + 1 < check[nx][ny][visited]:
                        dq.append((nx, ny, cost + 1, visited))
                        check[nx][ny][visited] = cost + 1

    if ret == sys.maxsize:
        print(-1)
    else:
        print(ret)

이 코드에서 가장 중요한 부분은 이 다음 노드를 검사해서 추가해주는 부분이다. 겹치는 경우를 큐에 넣지 않기 위해 다음과 같이 구성했다.
즉, 각 노드가 가질 수 있는 상태는 지금 내가 어디까지 방문해서 여기까지 왔다이다. 그렇기 때문에, 단순히 check 배열을 2차원 리스트로 만든 것이 아니라 방문한 상태까지 저장하기 위해 check[x][y][visited] 3차원으로 구성했다. 따라서 check에 있는 값 값과 비교해서 cost + 1 이 더 작으면 큐에 넣어주고 갱신해주면서 탐색을 이어나갈 수 있도록 했다.

if (nx, ny) in dirty:
    index = dirty[(nx, ny)]
    nextVisited = visited | (1 << index)
    if cost + 1 < check[nx][ny][nextVisited]:
        dq.append((nx,ny,cost+1, nextVisited))
        check[nx][ny][nextVisited] = cost + 1

else:
    if cost + 1 < check[nx][ny][visited]:
        dq.append((nx, ny, cost + 1, visited))
        check[nx][ny][visited] = cost + 1

---

다음 풀이는 처음 말한 방식이다. (sangahn0524 이 분 풀이 퍼옴)

from collections import deque
from itertools import permutations

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

    if w == 0 and h == 0:
        break

    room = [list(input()) for _ in range(h)]

    x = [-1,1,0,0]
    y = [0,0,-1,1]

    dirty_count = 0
    dirty_list = []
    dirty_distance = {}

    start_pos_row = 0
    start_pos_col = 0

    for row in range(h):
        for col in range(w):
            # 모든 경로를 지나야하니까 시작점도 더러운점이라고 본다
            if room[row][col] == 'o':
                start_pos_row = row
                start_pos_col = col
                dirty_count += 1
            elif room[row][col] == '*':
                dirty_list.append((row, col))
                dirty_count += 1
    dirty_list = [(start_pos_row, start_pos_col)] + dirty_list

    def bfs_find_distance(start_row, start_col):
        # 시작 위치에서 bfs해서 모든 먼지까지의 거리 파악
        q = deque()
        q.append((start_row, start_col))
        distance = [[0 for _ in range(w)] for _ in range(h)]
        cur_index = dirty_list.index((start_row, start_col))

        while q:
            row, col = q.popleft()

            for dir in range(4):
                new_row = row + x[dir]
                new_col = col + y[dir]

                if 0 <= new_row < h and 0 <= new_col < w and distance[new_row][new_col] == 0 and room[new_row][new_col] != 'x':
                    q.append((new_row, new_col))
                    distance[new_row][new_col] = distance[row][col] + 1
                    if room[new_row][new_col] == '*' and (start_row, start_col) != (new_row, new_col):
                        # 두 점 사이 거리를 저장한다. how?
                        # 이후 시작점과의 거리까지 저장해야한다.
                        # 어차피 모든 경로를 지나야하니까 시작점도 같이 보관하자
                        new_index = dirty_list.index((new_row, new_col))
                        if cur_index < new_index:
                            dirty_distance[(cur_index, new_index)] = distance[new_row][new_col]
                        else:
                            dirty_distance[(new_index, cur_index)] = distance[new_row][new_col]

    # 그래프 완성
    for dirty in dirty_list:
        bfs_find_distance(dirty[0], dirty[1])

    # 만약 도달할 수 없는점 있다면 break
    if len(dirty_distance) != (dirty_count * (dirty_count-1) / 2):
        print(-1)
        continue

    # 모든 경로를 지나면서 비용이 최소인 경로 찾기
    nodes = [i for i in range(1, len(dirty_list))]
    all_routes = list(permutations(nodes))
    min_cost = float('inf')

    for route in all_routes:
        cost = dirty_distance[(0, route[0])]
        for i in range(len(route)-1):
            min_route = min(route[i], route[i+1])
            max_route = max(route[i], route[i+1])
            cost += dirty_distance[(min_route, max_route)]
        min_cost = min(min_cost, cost)

    print(min_cost)