이 문제는 전형적인 BFS문제이다. BFS로 푸는건 맞는데 내가 BFS를 모른다는 생각이 들었다. 왜냐면 문제에서 최소 거리를 구하라고 했는데, BFS 자체가 왔던 길을 다시 되돌아 가지 않기 때문에 최소 거리가 보장된다는 것이다.
1. 문제 해설
이러한 지도가 있다고 하면, 다음과 같은 경로가 있을 수 있다. 이때 하단의 경로 중에서 첫 번째 경로가 가장 최소의 경로가 된다.
이때 지나가는 경로의 가중치를 모두 1이라고 한다면 최소 가중치의 합을 구하면 된다.
2. 어려웠던 점
1) 최소길이를 BFS로
BFS는 완전탐색의 일종인데, 내가 생각했던 BFS는 큐에 해당 점을 넣고 인접한 모든 점을 탐색한다. 그래서 최소가 아니라고 생각이 들었다.
위의 그림에서 첫 번째 예시와 두 번째 예시는 다르게 카운팅 되기때문에 둘다 최소가 될 수 있는 조건을 만족하는게 아닌가 싶었는데, 이미 첫 번째에서 방문한 점을 두 번째에서 다시 재방문 하기 때문에 후보가 될 수 없다.
이전에 방문했던 점을 다시 재방문 하지 않는다는 점에서 최소의 조건을 이미 만족시켜준다.
2) 가중치용 인접행렬
BFS를 풀이할 때에 방문하는 가중치의 합을 구하는 인접행렬을 추가로 설정해줘야 했다. 이 기법을 내가 활용할 줄 모르는 것 같았다.
이전에 거리두기 확인하기에서도 이런식으로 문제를 구현했는데, 그때와는 다르다고 생각했어서 처음에 구현하지 못했었다.
앞으로, 의미를 잘 파악하고 활용해야겠다.
3. 풀이
#일단 전체 길에 포함여부 확인
#이미 갔던 길은 다시 들어가면 노노링
#현재 위치에서 상하좌우를 확인하되, 해당 위치가 0이면 안됨
from collections import deque
def solution(maps):
confirm_point = [(-1,0),(1,0),(0,-1),(0,1)] #dy, dx
queue = deque()
queue.append((0,0))
graph = [[-1 for _ in range(len(maps[0]))] for _ in range(len(maps))]
graph[0][0] = 1
while queue:
start_point = queue.popleft()
for dy, dx in confirm_point:
y = dy+start_point[0]
x = dx+start_point[1]
if -1<y<len(maps) and -1<x<len(maps[0]) and maps[y][x]==1: #전체 map에 포함되는지?
if graph[y][x] ==-1:
graph[y][x] = graph[start_point[0]][start_point[1]] + 1
queue.append((y,x))
## 막혔던 점
## 2갈래가 나뉘어지면, 이후에는 어떻게 갈라서 코드를 작성할지 몰랐음
## 2갈래로 나눠 진다는 생각 자체가 잘못됨, 이미 앞에서부터 탐색 후 방문된 점을 돌았기 때문에 ...
## 그걸 graph가 해줌
## 인접행렬(graph)를 선언
return graph[-1][-1]