[Baekjoon] 로봇 청소기(python)

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

문제 접근

이 문제는 BFS + 순열을 이용한 문제였다.

 

더러운 칸의 갯수가 10개를 넘지 않기 때문에 최대 10! 만큼만 연산하면 되었기 때문이다.

 

그래서 탐색할 더러운 칸의 순서를 permutations 연산을 통해 순열을 구하고 BFS를 통해 하나씩 탐색하면서 지나치는 칸의 갯수를 세어주었다.

 

하지만 BFS를 통해 매번 칸의 갯수를 연산하는 방식은 시간초과를 해결할 수 없었고, 메모이제이션(Memoization)을 통해 각 더러운 칸 사이를 탐색할 때 지나치는 칸의 갯수를 저장하여 매번 연산하지 않도록 수정했다.

 

오답 코드

import sys
from itertools import permutations
from collections import deque


def get_dirty_room():
    result = []

    for i in range(h):
        for j in range(w):
            if room[i][j] == "*":
                result.append([i, j])

    return result


def get_robot():
    for i in range(h):
        for j in range(w):
            if room[i][j] == "o":
                return i, j


def bfs(start, end):
    visited = [[False] * w for _ in range(h)]
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    visited[start[0]][start[1]] = True
    q = deque()
    q.append([start[0], start[1], 0])

    while q:
        x, y, dist = q.popleft()

        if x == end[0] and y == end[1]:
            return dist

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

            if (
                nx < 0
                or nx >= h
                or ny < 0
                or ny >= w
                or room[nx][ny] == "x"
                or visited[nx][ny]
            ):
                continue

            q.append([nx, ny, dist + 1])
            visited[nx][ny] = True

    return -1


while True:
    w, h = list(map(int, sys.stdin.readline().split()))
    ans = sys.maxsize

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

    room = []

    for _ in range(h):
        room.append(list(sys.stdin.readline()[:-1]))
    robot = get_robot()

    dirty_room = get_dirty_room()
    permutation_list = list(permutations(dirty_room, len(dirty_room)))

    for dirty_room in permutation_list:
        start = robot
        total = 0

        for end in dirty_room:
            dist = bfs(start, end)

            start = end

            if dist == -1:
                total = -1
                break

            total += dist

        ans = min(ans, total)

    print(ans)

---

풀이 과정

1. 로봇 청소기가 모든 더러운 칸을 방문할 수 있는지 검사

로봇이 방문할 수 없는 더러운 칸이 존재하면 -1을 출력해야 하므로 BFS를 통해 모든 칸을 탐색하면서 로봇이 각 칸까지 이동해야할 거리를 계산한다.

2. 모든 더러운 칸 사이의 거리 계산

마찬가지로 각 더러운 칸을 출발점으로 두고 BFS를 통하여 다른 칸까지의 거리를 미리 계산해둔다. 미리 계산해서 dist배열에 저장해두어야 매번 연산하지 않으므로 시간초과를 방지할 수 있다.

def bfs(start):
    visited = [[0] * w for _ in range(h)]
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    q = deque()

    visited[start[0]][start[1]] = 1
    q.append([start[0], start[1]])

    while q:
        x, y = q.popleft()

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

            if (
                nx < 0
                or nx >= h
                or ny < 0
                or ny >= w
                or room[nx][ny] == "x"
                or visited[nx][ny]
            ):
                continue

            q.append([nx, ny])
            visited[nx][ny] = visited[x][y] + 1

    return visited

for i in range(dirty_room_count - 1):
    visited = bfs(dirty_room[i])

    for j in range(i + 1, dirty_room_count):
        dist[i][j] = visited[dirty_room[j][0]][dirty_room[j][1]] - 1
        dist[j][i] = dist[i][j]

3. 더러운 칸들의 탐색 순서 조합

순열을 통해 더러운 칸의 탐색 순서 리스트를 생성하고 총 거리를 계산한다.

for permu in permutations(range(dirty_room_count)):
    start = permu[0]

    # 로봇에서 해당 더러운 칸까지의 거리
    total = robot_to_dirty_room[start]

    for i in range(1, dirty_room_count):
        end = permu[i]

        total += dist[start][end]
        start = end

    ans = min(ans, total)

 

---

정답 코드

"""
    백준 4991번 로봇 청소기
"""
import sys
from itertools import permutations
from collections import deque


def get_dirty_room():
    result = []

    for i in range(h):
        for j in range(w):
            if room[i][j] == "*":
                result.append([i, j])

    return result


def get_robot():
    for i in range(h):
        for j in range(w):
            if room[i][j] == "o":
                return i, j


def bfs(start):
    visited = [[0] * w for _ in range(h)]
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]
    q = deque()

    visited[start[0]][start[1]] = 1
    q.append([start[0], start[1]])

    while q:
        x, y = q.popleft()

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

            if (
                nx < 0
                or nx >= h
                or ny < 0
                or ny >= w
                or room[nx][ny] == "x"
                or visited[nx][ny]
            ):
                continue

            q.append([nx, ny])
            visited[nx][ny] = visited[x][y] + 1

    return visited


while True:
    w, h = list(map(int, sys.stdin.readline().split()))
    ans = sys.maxsize

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

    room = []

    for _ in range(h):
        room.append(list(sys.stdin.readline()[:-1]))

    visited = bfs(get_robot())
    dirty_room = get_dirty_room()
    dirty_room_count = len(dirty_room)

    robot_to_dirty_room = [0] * dirty_room_count

    is_possible = True

    for i, pos in enumerate(dirty_room):
        if not visited[pos[0]][pos[1]]:
            is_possible = False
            break
        robot_to_dirty_room[i] += visited[pos[0]][pos[1]] - 1

    if not is_possible:
        print(-1)
        continue

    dist = [[0] * dirty_room_count for _ in range(dirty_room_count)]

    # 더러운 칸끼리 거리를 미리 계산(매번 bfs를 통하여 거리를 계산하면 시간초과)
    for i in range(dirty_room_count - 1):
        visited = bfs(dirty_room[i])

        for j in range(i + 1, dirty_room_count):
            dist[i][j] = visited[dirty_room[j][0]][dirty_room[j][1]] - 1
            dist[j][i] = dist[i][j]

    ans = sys.maxsize

    # 더러운 칸의 순서를 순열로 미리 구해놓는다.
    for permu in permutations(range(dirty_room_count)):
        start = permu[0]

        # 로봇에서 해당 더러운 칸까지의 거리
        total = robot_to_dirty_room[start]

        for i in range(1, dirty_room_count):
            end = permu[i]

            total += dist[start][end]
            start = end

        ans = min(ans, total)

    print(ans)