문제
https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
[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
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 집합 / [1차] 뉴스 클러스터링 (0) | 2025.10.01 |
|---|---|
| 프로그래머스 / 백트래킹 / 타겟 넘버 (0) | 2025.09.24 |
| 프로그래머스 / 해시 / 롤케이크 자르기 (0) | 2025.09.21 |
| 프로그래머스 / 큐 / 프로세스 (0) | 2025.09.21 |
| 프로그래머스 / 해시 / 전화번호 목록 (0) | 2025.09.20 |