이번 문제는 BFS와 permutations를 이용하여 해결하였다. 처음에는 permutations를 만들고, 각각의 점에서 점까지의 BFS를 계속해서 실행하도록 하였다. 답은 잘 도출되었지만, 당연히도 시간초과가 발생하였다.

이를 해결하기 위해 로봇에서부터 각 먼지까지의 거리를 구하고, 모든 먼지간의 거리를 구하여, 이 먼지들의 거리의 합이 가장 작은 것을 출력하도록 코드를 다시 작성하였고, 정답을 받을 수 있었다.

Code

초기 코드 (시간 초과)

from collections import deque
def get_sequence(cur, d):
    if cur == len(dust):
        dusts.append(d)
        return
    for i in range(len(dust)):
        if dust[i] not in set(d):
            get_sequence(cur+1, d+[dust[i]])
def cleaning(y1, x1, y2, x2):
    q = deque()
    q.append((y1, x1, 0))
    visited = [[False for _ in range(w)] for _ in range(h)]
    while q:
        y, x, time = q.popleft()
        if (y, x) == (y2, x2):
            return time
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] != 'x' and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx, time+1))
    return -1
while True:
    w, h = map(int, input().split())
    if (w, h) == (0, 0):
        break
    grid = [list(str(input())) for _ in range(h)]
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    dust = []
    robot = []
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '*':
                dust.append((i, j))
            if grid[i][j] == 'o':
                robot = [i, j]
    dusts = []
    get_sequence(0, [])
    answer = 1e9
    for i in range(len(dusts)):
        ans = 0
        chk = True
        tmp = cleaning(robot[0], robot[1], dusts[i][0][0], dusts[i][0][1])
        if tmp == -1:
            continue
        ans += tmp
        for j in range(len(dusts[i])-1):
            tmp = cleaning(dusts[i][j][0], dusts[i][j][1], dusts[i][j+1][0], dusts[i][j+1][1])
            if tmp == -1:
                chk = False
                break
            ans += tmp
            if ans > answer:
                chk = False
                break
        if chk:
            answer = min(answer, ans)
    if answer == 1e9:
        answer = -1
    print(answer)

정답 코드

from collections import deque
from itertools import permutations
def cleaning(y, x):
    q = deque()
    q.append((y, x))
    visited = [[0 for _ in range(w)] for _ in range(h)]
    visited[y][x] = 1
    while q:
        y, x = q.popleft()
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] != 'x' and not visited[ny][nx]:
                visited[ny][nx] = visited[y][x] + 1
                q.append((ny, nx))
    return visited
while True:
    w, h = map(int, input().split())
    if (w, h) == (0, 0):
        break
    grid = [list(str(input())) for _ in range(h)]
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    dust = []
    robot = []
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '*':
                dust.append((i, j))
            if grid[i][j] == 'o':
                robot = [i, j]
    r_d, chk = [], True
    c = cleaning(robot[0], robot[1])
    for y, x in dust:
        if not c[y][x]:
            chk = False
            break
        r_d.append(c[y][x]-1)
    if not chk:
        print(-1)
        continue
    d_d = [[0 for _ in range(len(dust))] for _ in range(len(dust))]
    for i in range(len(dust)-1):
        c = cleaning(dust[i][0], dust[i][1])
        for j in range(i+1, len(dust)):
            d_d[i][j] = c[dust[j][0]][dust[j][1]]-1
            d_d[j][i] = d_d[i][j]
    points = list(permutations([i for i in range(len(d_d))]))
    answer = 1e9
    for i in points:
        dist = 0
        dist += r_d[i[0]]
        start = i[0]
        for j in range(1, len(i)):
            end = i[j]
            dist += d_d[start][end]
            start = end
        answer = min(answer, dist)
    print(answer)