문제

BOJ 4991: 로봇 청소기 https://www.acmicpc.net/problem/4991

풀이

조건

• 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다.
• 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.
• 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다.
• 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.
• 방의 정보는 4가지 문자로만 이루어져 있다.
  • .: 깨끗한 칸
  • *: 더러운 칸
  • x: 가구
  • o: 로봇 청소기의 시작 위치
• 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구한다.

풀이 순서

• 처음에는 이동할 위치를 순열로 구하고 그 때 마다 BFS를 사용해 거리의 최솟값을 구했다.
  • 이 때 시간초과가 났다.
• 두번째는 각 먼지들과 청소기 초기 위치와의 최소 거리를 미리 구해 테이블(dist)에 저장했다.
  • 각 먼지들과 청소기 초기 위치와의 최소 거리는 BFS를 사용해 구했다.
  • 백트래킹을 사용해 이동할 위치의 순열을 구하는데 파라미터로 이동 거리를 넘겨주며 최단거리를 구했다.

코드

Python

import sys
from collections import deque

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


# 두 점 사이의 최소 거리 구하는 함수(BFS 사용)
def move_to_target(now_pos, target_pos):
    global w, h, board

    que = deque()
    is_visited = [[False for _ in range(w)] for _ in range(h)]

    x, y = now_pos
    que.append([x, y, 0])
    is_visited[x][y] = True

    while que:
        now_x, now_y, now_cnt = que.popleft()
        
        # 목적지 도달하면 최소 거리 반환하고 종료
        if now_x == target_pos[0] and now_y == target_pos[1]:
            return now_cnt

        for t in range(4):
            nx = now_x + dx[t]
            ny = now_y + dy[t]

            if nx < 0 or ny < 0 or nx >= h or ny >= w or board[nx][ny] == 'x':
                continue
            if is_visited[nx][ny]:
                continue

            que.append([nx, ny, now_cnt + 1])
            is_visited[nx][ny] = True
            
    # 도달 못하면 1e9 반환하고 종료
    return int(1e9)


# 방문할 먼지 위치들을 조합하는 함수
def make_combination(depth, target_cnt, comb, start_pos, now_dist):
    '''
    :param depth: 재귀 깊이 -> 지금까지 조합한 수의 개수
    :param target_cnt: 재귀 깊이 목표
    :param comb: 조합한 결과를 저장할 배열
    :param start_pos: 로봇 청소기가 출발할 위치
    :param now_dist: 현재까지 이동한 총 거리
    '''
    global result, check_, targets_
    
    # 현재 까지 만든 조합에서의 거리가 이미 구했던 최소 거리보다 크면 바로 종료
    # 백트래킹에서 가지치는 부분
    if now_dist >= result:
        return

    # 조합 다 만들었을 때 거리가 최소값인지 확인
    if depth == target_cnt:
        if now_dist < result:
            result = now_dist
        return
    
    # 먼지 위치들을 조합으로 만들기
    for i in range(target_cnt):
        if not check_[i]:
            # 다음으로 출발할 먼지까지의 거리 구하기
            n_dist = now_dist + dist[start_pos][i]

            comb.append(i)
            check_[i] = True

            make_combination(depth + 1, target_cnt, comb, i, n_dist)

            comb.pop()
            check_[i] = False


result = int(1e9)

while True:
    result = int(1e9)
    w, h = map(int, sys.stdin.readline().rstrip().split())
    if w == 0 and h == 0:
        break

    board = [list(sys.stdin.readline().rstrip()) for _ in range(h)]

    # 먼지 칸, 출발 칸 위치 저장
    targets_ = []
    start_pos_ = []
    for i in range(h):
        for j in range(w):
            if board[i][j] == '*':
                targets_.append([i, j])
            elif board[i][j] == 'o':
                start_pos_ = [i, j]
    
    # 먼지들 사이의 거리와 초기 청소기  위치와 먼지들 사이의 거리를 테이블에 미리 저장
    # 초기 청소기 위치는 마지막 인덱스에 넣음
    dist = [[int(1e9) for _ in range(len(targets_) + 1)] for _ in range(len(targets_) + 1)]

    # 먼지들끼리 거리
    for i in range(len(targets_)):
        for j in range(len(targets_)):
            cnt = move_to_target(targets_[i], targets_[j])
            dist[i][j] = cnt
    # 먼지 ~ 초기 청소기 위치 거리
    for i in range(len(targets_)):
        cnt = move_to_target(start_pos_, targets_[i])
        dist[len(targets_)][i] = cnt
        dist[i][len(targets_)] = cnt
    dist[len(targets_)][len(targets_)] = 0

    # 더러운 칸 찾아가는 순서를 조합으로 구함
    check_ = [False for _ in range(len(targets_))]
    combs_ = []
    make_combination(0, len(targets_), combs_, len(targets_), 0)

    if result != int(1e9):
        print(result)
    else:
        print(-1)

정리

• 미리 각 지점 사이의 거리를 테이블에 저장해 순열을 구할 때(백트래킹) 파라미터로 해당 값을 넘겨주는 방법을 배웠다.