백준 4991번 로봇 청소기

1. 문제 설명

문제링크

오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다.

방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다.

일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 

로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러 번 방문할 수 있다.

방의 정보가 주어졌을 때, 더러운 칸을 모두 깨끗한 칸으로 만드는데 필요한 이동 횟수의 최솟값을 구하는 프로그램을 작성하시오.

• 입력
  • 입력은 여러 개의 테스트케이스로 이루어져 있다.각 테스트 케이스의 첫째 줄에는 방의 가로 크기 w와 세로 크기 h가 주어진다. (1 ≤ w, h ≤ 20) 둘째 줄부터 h개의 줄에는 방의 정보가 주어진다. 방의 정보는 4가지 문자로만 이루어져 있으며, 각 문자의 의미는 다음과 같다.
  • .: 깨끗한 칸
  • *: 더러운 칸
  • x: 가구
  • 로봇 청소기의 시작 위치
  • 더러운 칸의 개수는 10개를 넘지 않으며, 로봇 청소기의 개수는 항상 하나이다.  입력의 마지막 줄에는 0이 두 개 주어진다.
• 출력
  • 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다.

2. 코드

import sys
from collections import deque
from itertools import permutations

input = sys.stdin.readline

# 4방향 탐색
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(a, b):
    queue = deque()
    queue.append((a, b))
    
    # 거리 값을 표기 하기 위한 이중 리스트
    v = [[0] * w for _ in range(h)]
    
    # 처음 도착한 곳은 거리는 0이지만 코드상의 이유로 1로 표기
    v[a][b] = 1
    
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            # 범위를 벗어 나지 않고 한번도 방문 하지 않았던 곳이라면
            if 0 <= nx < h and 0 <= ny < w and not v[nx][ny]:
                # 그리고 가구가 아니라면
                if maps[nx][ny] != "x":
                    # 전 칸 기준으로 이동거리 값 표기
                    v[nx][ny] = v[x][y] + 1
                    queue.append((nx, ny))
    return v
while True:
    w, h = map(int, input().split())
    # w, h 둘다 0 이라면 무한 루프 종료
    if not w and not h:
        break
    maps = []
    r_x, r_y = 0, 0 # 로봇의 위치를 받을 x, y
    trash = [] # 더러운 칸을 받을 리스트

    for i in range(h):
        row = list(map(str, input().rstrip()))
        for j in range(w):
            if row[j] == "*":
                trash.append((i, j))
            elif row[j] == "o":
                r_x, r_y = i, j
        maps.append(row)
    r_ftd = [0] * len(trash) # 로봇을 기준으로 첫 번째로 청소 할 더러운 칸 까지의 거리를 담을 리스트
    check = False # 가구에 막혀 갈 수있는지 없는지 판단 할 플래그

    v = bfs(r_x, r_y) # 로봇을 기준으로 bfs을 하여 최솟 값으로 갈수 있는 곳을 표시!!!

    for i, xy in enumerate(trash): # 더러운 칸의 순서 와 위치를 뽑기 위해 enumerate 실행
        k = v[xy[0]][xy[1]] - 1 # 로봇 기준으로 첫번째 더러운 칸들의 거리 값
        if not v[xy[0]][xy[1]]: # 만약 도달 하지 못한다면
            print(-1) # 출력
            check = True # 플래그 수정
            break
        r_ftd[i] += k # 거리 값 더해주기
    # 만약 도달 할수 있는 곳이라면
    if not check:
        # 각 더러운 칸 들 끼리 거리 값을 나타 내기 위한 이중 리스트
        dists = [[0] * len(trash) for _ in range(len(trash))]

        # 각 더러운 칸들 끼리 거리 값을 나타 내기 위한 이중문
        for i in range(len(trash) - 1):
            # 거리 값을 표시 하기 위한 bfs 실시
            v = bfs(trash[i][0], trash[i][1])

            # ex) 첫 번째 더러운 칸을 기준으로 두번째, 세번째 ... n번째 칸 마다 거리 값을 표기
            for j in range(i + 1, len(trash)):
                dists[i][j] = v[trash[j][0]][trash[j][1]] - 1
                dists[j][i] = dists[i][j]
        # 최솟값 비교를 위함
        ans = int(1e9)

        # 순열로 모든 경우의 수 뽑아 내기
        for k in permutations(range(len(dists))):
            # 로봇 기준으로 첫번째 더러운 칸은 아까 저장했던 (각각의 첫번째 더러운 칸 거리)값으로 시작
            t = r_ftd[k[0]]

            # 시작도 여기!!
            start = k[0]

            for i in range(1, len(k)):
                # 도착지점두 다음 지점이다.
                end = k[i]
                # 거리 값을 더해주고
                t += dists[start][end]
                # 시작 지점을 도착지점으로 변경
                start = end
            # 최솟값 비교
            ans = min(ans, t)
        # 출력력
        print(ans)

3. 회고

Q. 문제를 보고 든 생각

• 더러운 칸이 10칸이 넘지 않는다 라는 문제 설명을 보고 더러운 칸을 기준으로 순열을 하고 그 값을 기준으로 BFS 최솟 값으로 이동하게 해서 그 거리 값을 더 해 나가면 해결 할수 있을 줄 알았다.
• 하지만 시간 초과가 나왔고 다른 방식을 찾았어야 했다.

※ 문제 해결 순서

1. 로봇 청소기, 더러운 칸의 위치를 구한다. 더러운 칸의 좌표를 trash에 담는다.
2. 첫 번째로 청소하게 될 더러운 칸까지의 거리는 '로봇 청소기'위치에서 해당 칸까지의 거리이다. '로봇 청소기 에서 (모든)더러운 칸'의 거리를 구한다. → BFS를 이용하여 '더러운 칸'까지의 거리를 r_ftd(robot_first_trash_distance 를 줄여서.. 이름을 지어봣다) 리스트담는다.
3. 2번에서 만약 '로봇 청소기'가 '가구(x)'의 배치로 인하여 방문할 수 없는 칸이 나타나면(visited 값이 0이면) '-1'을 출력하고 진행을 멈춘다.
4. 로봇 청소기가 처음 청소할 칸을 정하게 되면 남은 모든 더러운 칸들을 청소하는데 소요되는 거리는 각 칸의 거리의 총합이다. 따라서, 모든 더러운 칸 사이의 거리를 우선 구한다. → dists
5. 모두 깨끗한 칸으로 바꾸는 이동횟수는 청소하려는 칸의 '순서'에 따라 달라진다. 즉, 순열을 이용하여 청소하려는 칸의 순서를 정하고 4번에서 구한 거리를 이용하여 정답을 도출한다.

4. 고쳐야 할점

변수명 등등 구현 요소가 많아 더 많이 연습해야 할 것 같다는 생각이 들었다.