[풀이 방법]
- 그래프 탐색 문제로 bfs 활용
- 경유지가 있으므로, (시작점에서 경유지까지의 최단거리 + 경유지에서 끝점까지의 최단거리)를 계산
- 미로를 탈출 할 수 없는 경우는 시작점에서부터 레버까지 도달하지 못하는 경우와 레버에서 끝점 까지 도달하지 못하는 경우가 있음
[풀이 코드]
from collections import deque
def search(r, c, maps, distance):
visited = []
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
q = deque([(r, c)])
while q:
x, y = q.popleft()
if (x, y) in visited:
continue
visited.append((x, y))
for dx, dy in direction:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= len(maps) or ny < 0 or ny >= len(maps[0]) or maps[nx][ny] == 'X' or (nx, ny) in visited:
continue
distance[nx][ny] = distance[x][y] + 1
q.append((nx, ny))
def solution(maps):
answer = 0
maps = [list(line) for line in maps]
distance = [[0] * len(maps[0]) for _ in range(len(maps))]
sr, sc, lr, lc, er, ec = 0, 0, 0, 0, 0, 0
for i in range(len(maps)):
if 'S' in maps[i]:
sr, sc = i, maps[i].index('S')
if 'L' in maps[i]:
lr, lc = i, maps[i].index('L')
if 'E' in maps[i]:
er, ec = i, maps[i].index('E')
search(sr, sc, maps, distance)
if distance[lr][lc] == 0:
return -1
answer += distance[lr][lc]
distance = [[0] * len(maps[0]) for _ in range(len(maps))]
search(lr, lc, maps, distance)
if distance[er][ec] == 0:
return -1
return answer + distance[er][ec]