[DFS/BFS] 미로 탈출

출처 - [책] 이것이 코딩테스트다 with Python

문제

N*M 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리 괴물이 있어 이를 피해 탈출해야 한다. 동빈의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이 때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다.
미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오

예시

input                 output

5 6                   10  
101010
111111
000001
111111
111111

코드- BFS 이용

내가 푼 코드

from collections import deque 

#n,m = map(int, input().split()) #첫째줄 입력
#graph=[]
#for i in range(n):
#    graph.append(list(map(int, input())))

def bfs(sx,sy):
    queue = deque() 
    queue.append([sx,sy])
    
    while queue:
        x,y= queue.popleft()
        #print(x,y) 
        if x-1>-1:
            if graph[x-1][y]==1:
                graph[x-1][y]= graph[x][y]+1
                queue.append([x-1,y])
        if x+1<n:
            if graph[x+1][y]==1:
                graph[x+1][y]= graph[x][y]+1
                queue.append([x+1,y])
        if y-1>-1:
            if graph[x][y-1]==1:
                graph[x][y-1]= graph[x][y]+1
                queue.append([x,y-1])
        if y+1<m:
            if graph[x][y+1]==1:    
                graph[x][y+1]= graph[x][y]+1
                queue.append([x,y+1])
        
     return graph[n-1][m-1]
     
     
     
result= bfs(0,0)

print(result)

더럽죠?

💡 중복되는 if문을 제거해주기 위해서 방향 배열을 만들어줍니다.

#수정부분 코드만
dx=[-1,1,0,0]
dy=[0,0,-1,1]

def bfs(sx,sy):
    queue = deque()
    queue.append([sx,sy])
    
    while queue:
        x,y= queue.popleft()
        #print(x,y) 
        for i in range(n):
        	nx=x+dx[i]
        	ny=y+dy[i]
        	
            if nx<0 or nx>=n or ny<0 or ny>=m:
            	continue #범위 밖이면 무시하고 다음 루프를 돌린다.
            if graph[nx][ny]=1:
      			graph[nx][ny]+=graph[x][y] #방문했다는 표시 + 지나간 거리를 표시
                queue.append([nx,ny])
     return graph[n-1][m-1]
     

dx,dy 배열을 이용해서 구현하면 코드의 중복이 사라져 간결해집니다.

💡 BFS를 이용한 풀이가 더 적절한 이유:
아이스크림 개수를 구하는 문제와 달리 모든 노드를 탐색하지 않고 (N,M)의 위치에만 도달하면 되기 때문에 BFS를 이용해서 푸는 것이 더 적절하다고 할 수 있다.

코드 - DFS이용

def dfs(x,y):
    
    if x<0 or x>=n or y<0 or y>=m: #좌표의 위치가 범위 밖일 때는 return
        return graph[n-1][m-1]
    if graph[x][y]==0:
        return graph[n-1][m-1]
    
    print(x,y,end='\n')
    if x+1<n and graph[x+1][y]==1:
        graph[x+1][y]+=graph[x][y]
        dfs(x+1,y) 
    if x-1>-1 and graph[x-1][y]==1:
        graph[x-1][y]+=graph[x][y]
        dfs(x+1,y) 
    if y+1<m and graph[x][y+1]==1:
        graph[x][y+1]+=graph[x][y]
        dfs(x,y+1) 
    if y-1>-1 and graph[x][y-1]==1:
        graph[x][y-1]+=graph[x][y]
        dfs(x,y-1) 
    return graph[n-1][m-1]

dx,dy 배열을 사용해서 풀지 않아서 마찬가지로 더럽다.

음료수 얼려먹기 문제와 비슷하다고 생각하여 DFS로도 풀어보았다.
그러나 굳이 재귀를 이용하지 않아도 되고, 이렇게 하면 모든 노드를 방문하기 때문에 BFS가 더 효율적이라고 할 수 있다.

DFS	BFS

;; 아무튼 차이가 날겁니다...

BFS를 이용해서 탐색을 하다가 graph[x][y]==1조건을 통과해서 graph[0][0]로 다시 돌아가는 부분이 생기는데 이 부분을 처리해주면 DFS보다 더 적은 노드 수로 탐색할 것으로 예상된다.