Programmers _ 게임 맵 최단거리 _ 파이썬

📃 문제

프로그래머스 게임 맵 최단거리

알고리즘 - BFS, Queue

• BFS
  가중치가 없는 그래프에서 최단 경로
  ** 가중치가 있는 양수 그래프라면 다익스트라

조건

• 시작 인덱스 [0,0], 도착점 인덱스 [n-1, m-1] (단, n은 입력받는 map의 행, m은 열의 길이)
• 도착하지 못하는 maps가 주어지면 -1 반환.
  -> 도착점의 바로 위, 바로 왼쪽만 조사하면 안된다!!!!. 도착점과 좀 떨어져서 가로막고 있을 수도 있음
  -> 큐를 비웠을 때 도착점에 도착했는지 안했는지 따져야한다.

💡 풀이 과정

1) DFS 시도 🤯

시간초과

import copy
mincnt = 100001
def solution(maps):
    direction = [[0,1],[0,-1],[1,0],[-1,0]]
    n, m = len(maps), len(maps[0])
    if maps[n-2][m-1] ==0 and (m>1 and maps[n-1][m-2]==0) :
        #본 위치에서 하나 위 and 본위치에서 하나 왼쪽
        return -1
    cnt = 0
    visited = copy.deepcopy(maps)
    def move(i,j, visited,cnt):
        global mincnt
        if i<0 or i>=n or j<0 or j>=m: return
        if visited[i][j] == 0 or visited[i][j] == 2: return
        cnt+=1
        if i==n-1 and j==m-1:
            if cnt<mincnt : mincnt=cnt
            return
        visited[i][j]=2 #방문했다면 2
        if j<m-1: move(i,j+1,visited,cnt)
        if j > 0 : move(i,j-1,visited,cnt)
        if i<n-1: move(i+1,j,visited,cnt)
        if i >0 :move(i-1,j,visited,cnt)
    move(0,0,visited,cnt)
    print(mincnt)
    return mincnt

DFS를 사용하면 도착점 도착까지 가능한 경우에 대해 너무 많은 호출 발생.

2) BFS 🥳

• Idea :
  현재 위치로부터 갈 수 있는 곳을 모두 큐에 삽입.
  팝을 해가면서 반복
  큐를 비웠을 때 위치가 도착점이 아니라면 도착할 수 없는 맵이므로 -1 반환해야함 !!

import copy
from collections import deque
mincnt = 100001
def solution(maps):
    global mincnt
    n, m = len(maps), len(maps[0])
    if maps[n-2][m-1] ==0 and (m>1 and maps[n-1][m-2]==0) :
        # 본 위치에서 하나 위 and 본위치에서 하나 왼쪽
        # 첫번째 예외 처리, 전체 예외처리는 마지막에 한번 더
        return -1
    queue = deque([[0,0,1]])
    while queue:
        i,j,cnt = queue.popleft()
        if i==n-1 and j==m-1:
            mincnt = min(mincnt, cnt)
            break
        if maps[i][j] != 1:
            continue
        maps[i][j] = 2

        if j<m-1: queue.append([i,j+1,cnt+1])
        if j > 0 : queue.append([i,j-1,cnt+1])
        if i<n-1: queue.append([i+1,j,cnt+1])
        if i >0 :queue.append([i-1,j,cnt+1])
        
    if mincnt == 100001 : #도착점에 도착하지 못했다면 mincnt를 갱신하지 못했을 것이므로
        return -1
    return mincnt

🔍 정리 & 배운 것

from collections import deque

>기본 구현 코드
queue = deque()
queue = deque([]) #초기 값을 줄땐 배열에 담아서

while queue: #queue가 비어있지 않는 한 계속
	q = queue.popleft()
    if not visited q: # 방문하지 않은 노드라면,
    	# 작업