프로그래머스/LV2
[프로그래머스 Lv2,python]- 게임 맵 최단거리
chyam_eun
2025. 1. 17. 12:16
https://school.programmers.co.kr/learn/courses/30/lessons/1844
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
from collections import deque
def bfs(start,maps):
n,m=len(maps),len(maps[0]) # n행 m열
visited=[[0]*m for _ in range(n)] # 방문여부
queue=deque([(start[0],start[1],1)]) # 큐생성
visited[start[0]][start[1]]=1 # 방문함
direct=[(1,0),(0,1),(-1,0),(0,-1)] # 아래,오른쪽,위,왼쪽 순서대로
while queue:
v=queue.popleft() # 큐 반환
x,y,cnt=v[0],v[1],v[2]
if x==n-1 and y==m-1: # 상대 진영에 도달하면
return cnt
for a in direct:
if 0<=x+a[0]<n and 0<=y+a[1]<m and visited[x+a[0]][y+a[1]]==0 and maps[x+a[0]][y+a[1]]==1: # 방향을 움직였을때 0이상 n또는 m미만, 방문하지않고 벽이 아닐때
queue.append([x+a[0],y+a[1],cnt+1]) # 큐에 추가
visited[x+a[0]][y+a[1]]=1 # 방문여부
return -1
def solution(maps):
cnt=bfs((0,0),maps)
return cnt
최단거리여서 bfs를 사용해주었다.