BFS] 미로 탈출 ( feat. 이코테 2021 강의 몰아보기 문제 )

DFS와 쌍으로 이루는 BFS 관련 문제이다. 물론 DFS로 풀수도 있고 BFS로 풀수 있지만,

 

풀이방법이 다르고, 어떤 문제에선 DFS로 풀면 너무 오래걸리고, 그런 문제들이 존재하기 때문에 두가지에 대해서

 

잘 알아두고 적절한 알고리즘을 대입하여 푸는 것이 중요한 것 같다.

 

< 문제 >

주어지는 N*M 미로판에서 시작 지점 (1,1) 에서 시작하여 탈출 지점인 (N,M) 까지의 최단 경로를 구해야하며,

1은 지나다닐 수 있는 길이고, 0은 괴물이 있이 지나갈 수 없는 길입니다. ( 시작점 끝점을 포함한 최단 경로 )

( 탈출 할 수 없는 경우는 없습니다. )

 

< 예시 >

input :                  output:

111                        5

001

001

 

< 해결 아이디어 >

BFS 해결법으로 시작지점으로 부터 모든 노드를 검사하는 방법을 사용합니다. ( 상하좌우 )

모든 시작점은 (1,1)로 동일합니다. 모든 끝점은 (n-1,m-1) 로 동일합니다.

 

(1,1)에서 시작하여 상하좌우 검사하였을 때, 이동 가능한 노드에 대해서 처음 방문하는 경우에만 ( 최단경로를 찾기위한 )

노드 값을 직전 노드의 값에 1을 더해줍니다. 끝까지 움직였을때, 끝 점 노드가 가지는 값이 최단 경로가 됩니다.

 

< 문제 풀이 >

 

from collections import deque
# 이번 문제에서는 queue 자료형을 사용한다.

n, m = map(int,input().split())

graph = []
for i in range(n):
    graph.append(list(map(int,input())))
# 기존 입력은 DFS와 동일하여 그대로 사용 가능

dx=[-1,1,0,0]
dy=[0,0,-1,1]
# 상하좌우 이동 값에 대한 내용 리스트 

def bfs(x,y):
    q = deque() # 노드 검사를 위해 담아둘 Queue 자료형 선언
    q.append((x,y)) # q에 상하좌우 검사를 위한 노드 값 삽입
    while q: # Queue에 값이 없으면 모든 작업 완료
        x,y = q.popleft() # Queue 자료형이라 앞의 값부터 얻어온다.
        for i in range(4): # 상하좌우 검사를 위한 로직
            nx = x+dx[i]
            ny = y+dy[i]
            if nx < 0 or nx>=n or ny < 0 or ny >= m: # 미로 밖으로 넘어가면 pass
                continue
            if graph[nx][ny] == 0: # 방문할수 없는 ( 괴물이 있는 곳 ) 곳이면 pass
                continue
            if graph[nx][ny] == 1: # 최초 방문이면 최단경로로 가는 길이라 Queue에 삽입
                graph[nx][ny]= graph[x][y]+1
                q.append((nx,ny))

    return graph[n-1][m-1] # 탈출 지점에 값을 반환하면 최단 경로 반환 완료

print(bfs(0,0))