이 문제는 최단거리 이므로 bfs를 통해 구현해주면 된다.
bfs를 잘 모르는 지라 구글링을 하며 다른 사람의 답안을 참고 하며 작성해보았는데 처음에는 런타임 에러가 발생했다
그 이유는 보통은 x,y 좌표 순서가 (x,y) 이다 보니 다른 사람의 풀이에서 이 부분을 x y 순서로
대입했었다. 그러나 런타임 에러가 발생
생각해보니
[[1,0,1,1,1],
[1,0,1,0,1],
[1,0,1,1,1],
[1,1,1,0,1],
[0,0,0,0,1]]
이렇게 배열이 주어졌을 때 가로가 x 세로가 y 라고 하면 list[y][x] 이렇게 접근해야한다...(바보,,,)
평소의 기본 지식과 코딩할 때 사고해주어야 하는 부분이 충돌한 케이스이다.
이 부분을 맞게 수정하여
from collections import deque
def solution(maps):
q = deque()
n = len(maps) #y좌표 길이
m = len(maps[0]) #x좌표 길이
visited = [[False]*m for i in range(n)]
q.append((0,0)) #시작노드 두원소를 가진 튜플 추가
visited[0][0] = True #시작노드
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while q:
y,x = q.popleft()
for i in range(4): #상하좌우 4번 반복
nx = x+dx[i]
ny = y+dy[i]
if 0 <= nx < m and 0 <= ny < n and maps[ny][nx] == 1 :
if not visited[ny][nx]:
visited[ny][nx] = True
q.append((ny,nx))
maps[ny][nx] = maps[y][x]+1 #현재까지 누적 거리에 +1
answer = maps[n - 1][m - 1]
if answer == 1:
answer=-1
return answer처음에 maps [ny][nx]에 왜 값을 더하는 지 왜 answer가 maps[n-1][m-1]이 되는지 납득을 하지 못했었다.
이 부분은 경로를 이동하면서 현재까지 이동한 누적거리를 계속해서 해당 좌표에 추가해주는 거라고 이해하면 된다. 고로 도착지에 넣은 숫자는 도착지에 오기까지 걸린 거리가 되기때문에 해당 부분을 출력하면 된다.
이때 도착지가 1 이라면 도착지에 도달한 적이 없다는 뜻이 되므로 -1 을 answer로 출력해주면 된다.
그리고 어떻게 상하좌우에 갈 수 있는 경로가 여러개가 있을 때 다 계산이 되는지 이해를 못했었는데
방문하지 않았고, 벽이 아닐 경우에 큐에 넣어주어 가능한 경로를 전부 계산해 경로를 지나갈 때마다 걸린 거리만큼 해당 좌표를 바꾸어 주고 return 값은 목적지의 좌표를 뽑아 목적지를 가는 데 걸린 거리만 출력하는 걸로 이해했다
아직 dfs, bfs 가 이해하는데 많이 어렵다..... 문제를 많이 푸는 게 답인 것 같다.
