[BFS] 프로그래머스 게임 맵 최단거리 python

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/1844

코딩테스트 연습 - 게임 맵 최단거리

2. 풀이

전형적인 BFS

map의 row col이 다를 수 있다는 점을 빼먹어서 틀렸다.

 

3. 구현

from collections import deque # deque import

d = [[1,0], [-1, 0], [0,1], [0,-1]]

def isValid(r,c, row, col):
    return (r>=0 and c>=0 and r<row and c< col)

def solution(maps):
    answer = 0
    row = len(maps)
    col = len(maps[0])
    q = deque()
    visit=[[-1 for _ in range(col)] for _ in range(row)] # map만들기
    
    q.append([0,0])
    visit[0][0]=1
    
    while q:
        cur = q.popleft() # q는 popleft()
        for idx in range(4):
            nr = cur[0]+d[idx][0]
            nc = cur[1]+d[idx][1]
            
            if not isValid(nr, nc, row, col): # ! 안쓰고 not 쓰기
                continue
            
            if visit[nr][nc]==-1 and maps[nr][nc]==1:
                q.append([nr, nc])
                visit[nr][nc]=visit[cur[0]][cur[1]]+1
            
    # print(visit)
    answer = visit[-1][-1] # 맨마지막 요소는 이렇게 쓸 수 있음
    return answer