찾아라 프로그래밍 마에스터 문제
문제 풀러 바로가기 👇👇👇👇👇👇
https://programmers.co.kr/learn/courses/30/lessons/1844
문제내용은 위 링크 참고바람
문제풀이
위 문제는 BFS(너비 우선 탐색)을 이용하면 아주 쉽게 풀 수 있는 문제이다. queue(deque 라이브러리 사용)를 이용해 지도의 좌표를 저장하고 차례대로 좌표를 꺼내 퍼트려나가면 된다. 방향은 위, 아래, 왼쪽, 오른쪽 총 4가지로 현재좌표에 방향을 적용했을 때 그 값이 유효하다면 현재좌표+1 값을 방향을 적용한 좌표에 넣어 현재 몇 칸을 거쳐왔는지 표시해주면 된다. 마지막으로 유효한 좌표를 queue에 삽입해준다.
퍼져나가는 도중에 나아갈 방향의 좌표에 해당하는 값이 1보다 크다면 이미 방문한 좌표이기 때문에 continue를 통해 무시해주면 된다. (이 논리를 적용해야 최단거리를 구할 수 있음)
마지막 리턴할 때 목표 좌표(n-1, m-1)를 리턴해주면 된다. 여기서 유의할 점은 목표지에 도달하지 못했을 때 -1을 리턴하는 것인데, 목표지의 값이 0이거나 1이면 도달하지 못한 것이므로 이 때 -1을 반환해주면 된다.
코드
def solution(maps):
from collections import deque
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
n = len(maps)
m = len(maps[0])
queue = deque()
queue.append((0, 0))
while queue:
x, y = queue.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if maps[nx][ny] > 1 or maps[nx][ny] == 0:
continue
if nx == 0 and ny == 0:
continue
queue.append((nx, ny))
maps[nx][ny] += maps[x][y]
return maps[n-1][m-1] if maps[n-1][m-1] > 1 else -1