백준 4991 로봇청소기

from collections import deque

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

while True:
    loopout = False
    w, h = map(int, input().split())
    if w == 0 and h == 0:
        break
    g = [input() for _ in range(h)]
    dirt = []
    for i in range(h):
        for j in range(w):
            if g[i][j] == 'o':
                rx, ry = i, j
                dirt.append((i, j))

    for i in range(h):
        for j in range(w):
            if g[i][j] == '*':
                dirt.append((i, j))

    def clean(g, rx, ry):
        check = [[-1] * w for _ in range(h)]
        q = deque()
        q.append((rx, ry))
        check[rx][ry] = 0
        while q:
            x, y = q.popleft()
            for i in range(4):
                nx, ny = x + dx[i], y +dy[i]
                if nx < 0 or ny < 0 or nx >= h or ny >= w:
                    continue
                if check[nx][ny] == -1 and g[nx][ny] != 'x':
                    check[nx][ny] = check[x][y] + 1
                    q.append((nx, ny))
        return check

    # 방문할 더러운 칸 순서를 순열로 저장후 최소 거리 구함
    # 더러운 칸 ~ 더러운 칸 거리를 순열에 저장
    dirttodirt = [[-1] * len(dirt) for _ in range(len(dirt))]

    for i in range(len(dirt)):
        x, y = dirt[i]
        check = clean(g, x, y)
        for j in range(len(dirt)):
            nx, ny = dirt[j]
            dirttodirt[i][j] = check[nx][ny]
            if dirttodirt[i][j] == -1:
                loopout = True
    if loopout == True:
        print(-1)
        continue

    ans = 21*21*11

    def dfs(l, visited):
        global ans
        if len(l) == len(dirt):
            rans = 0
            for j in range(len(l)-1):
                rans += dirttodirt[l[j]][l[j+1]]
            ans = min(rans, ans)
        for i in range(0, len(dirt)):
            tmp_visited = visited[:]
            if tmp_visited[i] == -1:
                tmp_visited[i] = 0
                dfs(l + [i], tmp_visited)

    visited = [-1] * len(dirt)
    visited[0] = 0
    dfs([0], visited)
    print(ans)

처음에 이동 -> bfs -> 이동 ->bfs ... 이런 식으로 해서 시간 초과
각각을 시작점으로 bfs로 깨끗한 칸, 더러운칸 서로서로 간 거리를 구함 -> dfs로 순열 구해서 최솟값 구함