[백준 - Python] 4991 - 로봇 청소기

0. 문제 링크

 

 

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

4991번: 로봇 청소기

---

1. 풀이 방법

 

 

TSP로 문제를 풀었음  
BFS를 사용하여 청소기와 쓰레기들의 거리, 쓰레기들 사이의 거리를 모두 파악함  
이후 순열을 사용하여 청소기와 쓰레기를 한 줄로 잇는 최단 거리를 파악함  

 

그러나 효율성이 낮으므로, 이 방법 대신 다른 방법을 사용하면 좋을 듯

다른 방법으로는 각 쓰레기에 먼저 방문하는 노드의 경로들을 저장해서 처리하는 방법이 있음

이때 중복은 넣지 않고, (왜냐면 BFS에 의해 먼저 도착하는 경로가 더 빠름을 보장하기 때문)

이런 방식으로 최종적으로 어떤 쓰레기에 모든 경로를 경유했던 노드가 도착하면 그것을 답으로 내면 될 듯

---

2. 코드

 

 

import sys
from collections import deque
import itertools

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


def bfs(board, y, x):
    dq = deque([[y, x]])
    dist = [[-1] * w for _ in range(h)]        # 어느 한 정점에서 다른 정점까지의 거리를 나타내는 리스트
    dist[y][x] = 0
    while dq:
        for _ in range(len(dq)):
            y, x = dq.popleft()
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                if 0 <= ny < h and 0 <= nx < w and dist[ny][nx] == -1:
                    # 방문하지 않았다면 방문한다.
                    # 이미 방문한 정점이라면 최적이 보장되므로 방문할 필요가 없다.
                    if board[ny][nx] != 'x':
                        dq.append([ny, nx])
                        dist[ny][nx] = dist[y][x] + 1

    return dist


def sol(w, h):
    board = [[b for b in list(sys.stdin.readline().strip())] for _ in range(h)]

    pos = []        # 청소기와 쓰레기의 좌표
    for y in range(h):
        for x in range(w):
            if board[y][x] == '*':
                pos.append((y, x))
            elif board[y][x] == 'o':
                pos.insert(0, (y, x))       # 청소기는 항상 0에 들어가야 함

    flag = True
    l = len(pos)
    check = [[0] * l for _ in range(l)]     # 0번 인덱스는 청소기, 1, 2, ... , n은 쓰레기

    for i, p in enumerate(pos):     # 한 정점에서 다른 정점까지의 거리를 파악함
        if flag:
            dist = bfs(board, *p)       # bfs를 사용하여 한 정점에서 다른 정점까지의 거리를 찾음
            for j, n_p in enumerate(pos):       # 인접 행렬에 집어넣음
                if (d := dist[n_p[0]][n_p[1]]) == -1:
                    print(-1)
                    flag = False
                    break
                check[i][j] = d

    if flag:
        minimum = float('inf')
        for it in itertools.permutations(range(1, l), l - 1):
            # 시작은 항상 0(청소기)이므로, 쓰레기에서 다른 쓰레기로 이동하는 경우의 수를 모두 살펴봄
            dist = 0
            it = tuple([0]) + it
            for j in range(l - 1):      # 모든 거리를 구해봄
                dist += check[it[j]][it[j + 1]]
            minimum = dist if dist < minimum else minimum       # 거기서 최적을 찾음
        print(minimum)


while True:
    w, h = map(int, sys.stdin.readline().split())
    if not w and not h:
        exit(0)
    sol(w, h)

---

3. 마무리

 

 

알고리즘 분류에 비트마스킹이 있던데, 어떻게 적용해야 할지 모르겠음  
그리고 굳이 TSP를 쓰지 않아도 풀 수 있는 방법이 있을 것 같은데  

BFS는 서브로 쓰고, TSP를 조금 중점적으로 풀어야 했는데, 너무 시작부터 BFS만 생각했던 것 같음
아무튼 itertools의 메소드를 알 수 있어서 좋았던 것 같음