[백준] 4991번 로봇청소기 (파이썬)

난이도 : GOLD I

문제링크 : https://www.acmicpc.net/problem/4991

문제해결 아이디어

처음 내가 생각한 방법은 다음과 같다.

• 순열을 통해서 먼지순서를 정하고
• 각각의 먼지순서간의 최단거리의 합을 구하고 (bfs 사용)
• 그중에 가장 낮은 값

이렇게 구하니 시간초과가 났다. 사실 먼지 개수가 10까지 되서 10! 10 bfs 니까 당연한 결과이기도 하다.

소스코드(오답)

import sys
import copy
import heapq
from itertools import permutations, combinations
from collections import deque

input = sys.stdin.readline

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

# 순열을 통해서 먼지순서를 정하고
# 각각 먼지간의 최단거리의 합을 구하고 (bfs 사용)
# 그중에 가장 낮은 값 = 시간초과

# 청소기로부터의 먼지 거리를 구하고 (1차원 배열)
# 2차원 배열로 각각의 먼지간의 거리를 구한다.
# 순열을 통해서 청소하는 먼지의 순서를 섞는다.
  # 2차원 배열을 통해 각각의 먼지거리의 합을 구한다.
  # 최솟값 비교.

def bfs(x, y, a, b):
    q = deque()
    q.append((x, y))

    visited = [[0] * m for _ in range(n)]
    visited[x][y] = 1

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

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

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and board[nx][ny] != 'x':
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))

    if visited[a][b]:
        return visited[a][b] - 1
    else:
        return -1


while True:
    m, n = map(int, input().split())

    if m == 0 and n == 0:
        break

    board = []
    cnt = 0
    dust = []
    for i in range(n):
        board.append(list(input().strip()))
        for j in range(m):
            if board[i][j] == 'o':
                start = (i, j)
            if board[i][j] == '*':
                cnt += 1
                dust.append((i, j))

    res = []

    for combi in permutations(dust, len(dust)):
        flag = False
        ans = 0
        tmp = (start[0], start[1])
        for i in range(len(combi)):
            k = bfs(tmp[0], tmp[1], combi[i][0], combi[i][1])

            if k == -1:
                res = [-1]
                flag = True
                break
            else:
                ans += k
                tmp = (combi[i][0], combi[i][1])

        else:
            res.append(ans)
        if flag:
            break

    print(min(res))

어느부분을 손대서 시간복잡도를 줄여야 할지 감을 못잡겠어서 다른사람 풀이를 참고했다.

다른 사람의 순서는

• 청소기로부터의 먼지 거리를 구하고 (1차원 배열)
• 2차원 배열로 각각의 먼지간의 거리를 구한다.
• 순열을 통해서 청소하는 먼지의 순서를 섞는다.
  • 2차원 배열을 통해 각각의 먼지거리의 합을 구한다.
  • 최솟값 비교.

각 먼지를 돌면서 bfs를 통해 다른 먼지들간의 최단거리를 이차원배열에 저장함으로써 시간 복잡도를 파멸적으로 줄였다..

소스코드(solved)

import sys
import copy
import heapq
from itertools import permutations, combinations
from collections import deque

input = sys.stdin.readline

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

def bfs(x, y):
    q = deque()
    q.append((x, y))

    visited = [[0] * m for _ in range(n)]
    visited[x][y] = 1

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

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

            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and board[nx][ny] != 'x':
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))

    return visited


while True:
    m, n = map(int, input().split())

    if m == 0 and n == 0:
        break

    board = []
    dust = []
    flag = False
    for i in range(n):
        board.append(list(input().strip()))
        for j in range(m):
            if board[i][j] == 'o':
                start = (i, j)
            if board[i][j] == '*':            
                dust.append((i, j))

    first_step = [0] * len(dust)

    v = bfs(start[0],start[1])
    for idx, co in enumerate(dust):
        if v[co[0]][co[1]]:
            first_step[idx] = v[co[0]][co[1]] - 1
        else:
            flag = True
            break

    if flag:
        print(-1)
        continue
        
    dust_dist = [[0]*len(dust) for _ in range(len(dust))]
    
    for i in range(len(dust)-1):
        v = bfs(dust[i][0],dust[i][1])
        for j in range(i+1, len(dust)):
            dust_dist[i][j] = v[dust[j][0]][dust[j][1]] -1
            dust_dist[j][i] = dust_dist[i][j]

    ans = int(1e9)    
    
    for nums in permutations(range(len(dust))):
        res = first_step[nums[0]]
        start = nums[0]
        for i in nums[1:]:
            res += dust_dist[start][i]
            start = i

        ans = min(res, ans)
    print(ans)