전공/프로그래머스
게임 맵 최단거리
yha97
2023. 9. 29. 00:38
날짜 : 2023. 09. 28
사용 언어 : python
문제
코드
from collections import deque
def solution(graph):
n, m = len(graph), len(graph[0])
for i in range(n):
for j in range(m):
if graph[i][j] == 1: graph[i][j] = 0
else: graph[i][j] = 1
answer = 0
queue = deque()
queue.append([0, 0])
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while queue:
x, y = queue.popleft()
if x == (n-1) and y == (m-1):
return graph[x][y] + 1
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if nx in range(n) and ny in range(m): # 범위 확인
if (nx, ny) != (0, 0) and graph[nx][ny] == 0: # 방문여부 체크
graph[nx][ny] = graph[x][y] + 1
queue.append([nx, ny])
return -1
풀이
- 일반적인 BFS로 풀이하는 문제였다.
- 따로 방문여부를 저장하는 리스트를 만들지 않고, 이동 가능한 칸은 0, 벽은 1로 하되, 이동한 거리를 저장하도록 움직일 때마다 해당 좌표에 가산하는 방식으로 큐를 돌렸다.
- 다만 문제의 조건에서 1이 이동 가능한 칸, 0이 벽으로 제시되었기 때문에 문제 처음에 1을 0으로, 0을 1로 변환하는 작업을 실시하였다.
알게된 점
-
참고 사이트
-