[백준]4991 로봇청소기

1.풀이

처음에 생각한 방법은 가장 가까운 먼지부터 먼저 방문하고, 그러한 먼지가 여러개일 경우를 dfs로 탐색해주는 그리디한 방법을 생각했다. 하지만 이는 다다음 먼지의 위치에 따라 더 긴 경로가 될 수 있다. 아래의 경우가 그 반례이다.

*	.	.	.	.	.
.	.	.	.	.	.
.	.	*	.	.	.
.	.	.	o	.	.
.	.	.	.	.	.
.	.	.	.	.	*

그리디하게 접근한다면 시작점에서 왼쪽위 먼지로 가야하지만, 그러면 총 이동거리는 16이된다.

하지만 제일 오른쪽 아래에 있는 먼지부터 먼저 접근하면 총 이동거리는 14가 된다.

따라서 모든 경우를 탐색해 주어야 한다.

(근데 2차원 평면이아닌, 1차원 직선에선 그리디하게 접근해도 되는거 같음..)

​

올바른 접근방법은

(1) 시작점에서 모든먼지까지의 위치를 구한다

(2) 위치를 구한 먼지로 이동해서 해당 먼지는 방문했으므로 "."으로 바꿔준다

(3) 그후 bfs를 통해 또 다른 먼지까지의 위치를 구한다

(4) (2),(3)을 반복한다

(근데 이런 방식은 이미 구한 먼지사이의 거리를 매번 다시 구한다. 먼지사이의 거리를 미리 한번만 구해서 필요할때만 써먹으면 수행시간이 더 빠를거 같다)

 

2.소스코드

from collections import deque
dR=[0,0,-1,1]
dC=[-1,1,0,0]

#map에 먼지 있으면 True
def isDirt(map):
    for i in range(h):
        for j in range(w):
            if map[i][j]=="*":
                return True
    return False

def bfs(startR,startC,nowMap,visited,dirtL):
    q = deque([[startR, startC]])
    while(q):
        r,c=q.popleft()
        for k in range(4):
            tempR=r+dR[k]
            tempC=c+dC[k]
            if 0<=tempR<h and 0<=tempC<w and visited[tempR][tempC]==-1:
                #깨끗한칸
                if nowMap[tempR][tempC]==".":
                    q.append([tempR,tempC])
                    visited[tempR][tempC]=visited[r][c]+1
                #더러운칸
                elif nowMap[tempR][tempC]=="*":
                    dirtL.append([tempR,tempC])
                    q.append([tempR,tempC])
                    visited[tempR][tempC]=visited[r][c]+1

def dfs(r,c,nowMap,cnt):
    #print(r,c)
    global ans
    if cnt>=ans:
        return True
    visited = [[-1 for j in range(w)] for i in range(h)]
    visited[r][c] = 0
    dirtL=[] #먼지위치저장
    bfs(r,c,nowMap,visited,dirtL)
    if dirtL:
        for i,j in dirtL:
            nowMap[i][j]="."
            if dfs(i,j,nowMap,cnt+visited[i][j]):
                nowMap[i][j] = "*"
            else:
                return False
        return True
    else:
        #먼지있으면
        if isDirt(nowMap):
            return False
        else:
            if ans>cnt:
                ans=cnt
            return True

while(1):
    w,h=map(int,input().split())
    if w==0 and h==0:
        break
    L=[]
    for i in range(h):
        temp=list(input())
        if "o" in temp:
            sR=i
            sC=temp.index("o")
        L.append(temp)
    ans=9876543210
    L[sR][sC]="."
    if dfs(sR,sC,L,0):
        print(ans)
    else:
        print(-1)