https://programmers.co.kr/learn/courses/30/lessons/1844
[0,0]번째칸에서 [n,m]칸으로 이동할 수 있는 최단 거리를 구하는 문제다.
이동할 수 없으면 -1을 출력하면 된다.
정처기랑 플조조 플젝,, 하느라 알고리즘 좀 쉬었더니 다 까먹었따.
큰일났다. ⸝⸝ʚ̴̶̷̆_ʚ̴̶̷̆⸝⸝ ,, .. ,
from collections import deque
from collections import defaultdict
def solution(maps):
n = len(maps)
m = len(maps[0])
dx = [-1,1,0,0]
dy = [0,0,-1,1]
graph = defaultdict(list)
for i,row in enumerate(maps):
for j,check in enumerate(row):
if check == 1:
for k in range(4):
nx = i + dx[k]
ny = j + dy[k]
if 0 <= nx < n and 0 <= ny < m:
if maps[nx][ny] == 1:
graph[(i,j)].append((nx,ny))
graph[(nx,ny)].append((i,j))
def bfs(graph,i,j):
visit = [[0] * m for _ in range(n)]
visit[0][0] = 1
queue = deque()
queue.append([(i,j),1])
while queue:
temp = queue.popleft()
location, cnt = temp[0], temp[1]
if location == (n-1,m-1):
return cnt
# 방문 안한 좌표일 때만 체크해준다.
if location not in visit:
x, y =location[0], location[1]
visit[x][y] = 1
#인근 좌표에 대해서 방문을 해준다.
if location in graph:
next_nodes = list(graph[location])
for next_node in next_nodes:
x, y =next_node[0], next_node[1]
if visit[x][y]== 0:
queue.append([next_node,cnt+1])
visit[x][y] = 1
answer = bfs(graph,0,0)
if (answer): return answer
return -1