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

문제

---

 

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

프로그래머스

 

 

입출력

---

 

 

해설

---

 

[0, 0]지점에 있는 게임 말을 n-1, m-1에 도달할 수 있는지와 도달할 수 있다면 얼마나 걸리는지에 관한 문제였다.

 

일단 최단거리로 움직인다는 가정 하 진행을 하는 것이었다.

 

이럴 때에는 BFS를 이용하여 풀이를 진행하는 것이 매우 좋다.

1 <= n, m <= 100 이기에 BFS를 이용하면 O(N * M)의 시간 복잡도를 가진다.

충분히 돌 수 있는 시간이기에 BFS를 이용하였다.

 

1. [0, 0] 지점 큐에 추가하기.

2. Boundary 체크, 방문 체크, 벽인지 체크.

3. 탈출 조건 확인

 

위와 같은 순서로 풀이를 진행하였다.

정답코드

---

'''
'25. 09. 23.(화)

bfs를 이용하여 움직이면 제일 빠르게 최단거리로 나갈 수 있다.

1. 0은 벽이 있는 자리, 1은 없는 자리이다.
2. 탈출할 수 있으면 answer, 아니면 -1을 리턴한다.
'''
from collections import deque
def bfs(n: int, m: int, board: list) -> int:
    #초기 위치 설정
    queue = deque([[0, 0]])
    
    #방문 배열
    visited = [[-1] * m for _ in range(n)]
    MOVE = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    
    #처음 위치 0
    visited[0][0] = 1
    while queue:
        x, y = queue.popleft()
        #탈출하였음
        if x == n - 1 and y == m - 1:
            return visited[x][y]
        for dx, dy in MOVE:
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:continue
            if visited[nx][ny]!= -1 or board[nx][ny] == 0:continue
            visited[nx][ny] = visited[x][y] + 1
            queue.append([nx, ny])
    #마지막에 탈출하지 못 하였을 때
    return -1
def solution(maps):
    return bfs(len(maps), len(maps[0]), maps)

 

깃허브 : https://buly.kr/APviu0A

유튜브 : https://youtu.be/6IR4lhZGUvg