알고리즘 유형 : BFS/DFS
풀이 참고 없이 스스로 풀었나요? : O
https://school.programmers.co.kr/learn/courses/30/lessons/1844
from collections import deque
def move(x, y):
yield (x-1, y)
yield (x+1, y)
yield (x, y-1)
yield (x, y+1)
def solution(maps):
answer = -1
row = len(maps)
col = len(maps[0])
visited = [[False]*col for _ in range(row)]
visited[0][0] = 1
q = deque([(0, 0)])
while q:
x, y = q.popleft()
if x == row-1 and y == col-1:
answer = visited[x][y]
break
for adj_x, adj_y in move(x, y):
if 0 <= adj_x < row and 0 <= adj_y < col:
if visited[adj_x][adj_y] == False and maps[adj_x][adj_y] == 1:
q.append((adj_x, adj_y))
visited[adj_x][adj_y] = visited[x][y] + 1
return answer
풀이 요약
큐에는 노드의 좌표를 넣어준다.
이 후 큐가 빌 때까지 큐에서 원소를 꺼내 목적지인지 검사하고, 목적지라면 그 때의 visited를 기록, 아니라면 인접 노드로 탐색을 이어나간다.
이 때 인접 노드로는 지도의 범위를 벗어나지 않는 한에서 동서남북 방향으로 진행한다.(제너레이터 활용)
인접 노드의 조건은, 지도의 범위를 벗어나지 않고 visited가 False(미방문)이며 벽이 아니여야(maps 값이 0이 아니여야 함)한다.
이를 만족하면 좌표를 큐에 넣고 visited를 이 전의 노드의 visited 값 + 1
로 갱신해주면 된다.
배운 점, 어려웠던 점