입출력 예시
maps | result |
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"] | 16 |
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"] | -1 |
나의 코드
from collections import deque
def solution(maps):
nrow, ncol = len(maps), len(maps[0])
def bfs(sr, sc, er, ec):
visited = set()
visited.add((sr, sc))
q = deque()
q.append((sr, sc, 0))
while len(q) > 0:
r, c, k = q.popleft()
if r == er and c == ec:
return k
neighbors = [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]
for nr, nc in neighbors:
if (0 <= nr < nrow) and (0 <= nc < ncol) and maps[nr][nc] != 'X' and (nr, nc) not in visited:
q.append((nr, nc, k+1))
visited.add((nr, nc))
return -1
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j] == 'S':
sr, sc = i, j
elif maps[i][j] == 'L':
lr, lc = i, j
elif maps[i][j] == 'E':
er, ec = i, j
s_l = bfs(sr, sc, lr, lc)
l_e = bfs(lr, lc, er, ec)
if (s_l == -1) or (l_e == -1):
return -1
else:
return s_l + l_e
Python
복사
기억할 점
•
BFS 구현
1.
queue로 구현, 각 element는 (position, path length) 담고 있어야 함.
2.
visited set 두고 새 노드 방문 시, 이미 방문했었는지 체크