99클럽 코테 스터디 12일차 TIL bfs/dfs : 프로그래머스 LV.2 게임 맵 최단거리 with Python

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

프로그래머스

문제는 위 쪽에서!

 

전형적인 최단거리 길찾기 문제!

from collections import deque

def solution(maps):
    answer = -1
    
    # 하, 상, 좌, 우
    dx, dy = (0, 0, -1, 1), (-1, 1, 0, 0)
    
    w, h = len(maps[0]), len(maps)
    visited = [[0 for _ in range(w)] for _ in range(h)]
    visited[0][0] = 1
    
    q = deque([[0, 0, 1]])
    while q:
        y, x, step = q.popleft()
        
        if y == h-1 and x == w-1:
            answer = step
            break
        
        for i in range(4):
            if 0 <= y+dy[i] < h and 0 <= x+dx[i] < w and maps[y+dy[i]][x+dx[i]] == 1:
                if visited[y+dy[i]][x+dx[i]] == 0:
                    q.append([y+dy[i], x+dx[i], step+1])
                    visited[y+dy[i]][x+dx[i]] = 1
    return answer

bfs를 사용해서 풀었다.

방문한 곳을 visited 처리하면서 가장 먼저 목적지에 도착하는 방법을 리턴!! 하는 방식이다.