문제
풀이
- 전형적인 BFS 문제입니다.
- 배운 대로 코딩합니다 ^^ https://blog.encrypted.gg/941
- maps가 주어집니다.
- vis는 원래 방문한 곳을 표시하여 다시 방문하지 않도록 하지만, 여기서는 더하여 해당 위치까지의 number of moves를 기록합니다.
- 처음 출발 지점은 [0,0]입니다. 단계별로 현 지점에서 갈 수 있는 지점들을 추가합니다.
- 추가된 지점 중에 어디를 먼저 가느냐에 따라, DFS(depth first search)와 BFS(breadth first search)가 구분됩니다.
- BFS는 추가된 지점들을 queue에 넣어서 가장 가까운 거리의 지점들부터 차례로 탐색합니다.
- 그러므로 어떤 한 지점에 도달할 수 있는 경로가 여러 가지가 있는 경우에, BFS를 사용하면 처음 출발한 곳에서 가장 가까운 거리에서 연결하는 방법으로 먼저 탐색할 수 있습니다.
queue.popleft()를 통해 BFS를 수행합니다.- 추가될 지점은, 전체영역 내에 있어야 하고, map에서 1로 표시된 곳이어야 하며, 이전에 방문한 적이 없어야 합니다.
- 이 문제에서는 vis에 방문 여부의 정보에 더하여, 출발 지점부터의 거리 정보를 추가합니다. 이처럼 vis에 다른 목적을 추가할 때는 조심해야 합니다.
- 이 문제의 해법 중에는 심지어 vis를 없애고 maps에 number of moves를 기록한 풀이도 있었습니다. 게임 맵 최단거리
결과
def f_t(id_t):
if id_t == 0:
maps, r = [[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]], 11
if id_t == 1:
maps, r = [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]], -1
return maps, r
from collections import deque
def solution(maps):
m = len(maps)
n = len(maps[0])
dx = [1,0,-1,0]
dy = [0,1,0,-1]
vis = [[0]*n for _ in range(m)]
queue = deque()
vis[0][0] = 1
queue.append((0,0))
while queue:
x0 = queue.popleft()
for i in range(4):
x = x0[0]+dx[i]
y = x0[1]+dy[i]
if 0<=x<m and 0<=y<n and vis[x][y] == 0 and maps[x][y] == 1:
vis[x][y] = vis[x0[0]][x0[1]] + 1
queue.append((x,y))
return -1 if vis[m-1][n-1] == 0 else vis[m-1][n-1]
for i in range(2):
print(f'test case {i}')
maps, r = f_t(i)
a = solution(maps)
print(a)
print(r) 
old engineer