https://school.programmers.co.kr/learn/courses/30/lessons/1844
from collections import deque
def solution(maps):
answer = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
dq = deque()
dq.append((0,0))
n = len(maps)
m = len(maps[0])
visited = [[0 for _ in range(m)] for _ in range(n)]
while dq:
x, y = dq.popleft()
visited[x][y] = 1
for i in range(4):
pointx = x + dx[i]
pointy = y + dy[i]
if 0 <= pointx < n and 0 <= pointy < m:
if not visited[pointx][pointy] and maps[pointx][pointy] == 1:
dq.append((pointx, pointy))
maps[pointx][pointy] = maps[x][y] + 1
print(dq)
print(visited)
if visited[n-1][m-1]:
answer = maps[n-1][m-1]
return answer
else:
return -1
- print(dq)찍어본거임
델타탐색을 했을 때 현재 위치를 기준으로 갈 수 있는 길이 두 군데 이상이면 deque에 두가지 지점, 현재 위치를 기준으로 갈 수 있는 길이 세 군데 이상이면 세가지 지점을 모두 append하는걸 확인할 수 있다.
->따라서 최단거리 기록은 어떻게 하나? - bfs의 특성상 탐색하는 상하좌우 끼리는 탐색의 우선순위가 없다. 그리고 거리는 탐색좌표가 변할때마다 +1씩 증가하는 형태이다. 그래서 좌표별로 최단거리를 기록하는 데이터를 하나 더 만든다. bfs의 특성상 탐색하는 상하좌우 끼리는 탐색의 우선순위가 없기 때문에 값이 이미 채워졌다면 다시 작성할 수 없다. 도착지의 최단거리는 도착지의 좌표에 대한 최단거리 데이터로 알 수 있다.
-> 결론적으로는 알아서 됨 (먼저 숫자가 채워져 있으면 이동 자체를 안하기 때문 대신 좌표별로 최단거리를 기록하는 데이터를 만들어야함)
회고
델타탐색의 가장 정석적인 문제가 아닐까 생각한다. 일단 dfs를 쓰면 시간초과가 난다고 한다(나중에 알아보기) 델타 탐색은 bfs에 더 잘 어울리는 것이 아닐까 싶다 사실 델타탐색만 알면 알고리즘 자체는 간단하다. 그냥 아직 방문하지 않았고 map이 1이면 음직일 수 있다는 얘기니까 dq에 append하고 visited 처리하면 된다 map에는 얼마만큼 음직였는지 알 수 있으니까 음직일때마다 1씩 추가하면 최종 구역에 적힌 숫자가 답이된다.
deque - popleft()
보통의 자료구조에서 pop연산이라고 하면 제일 끝에 요소가 삭제됨
이를 반대로 한 것이 바로 popleft -> 제일 앞의 요소 삭제
