•
문제 링크 : school.programmers.co.kr
•
문제 설명 : 레버가 존재하는 미로의 탈출 최소 시간을 구한다.
•
풀이 방법
◦
반드시 레버를 거쳐야하기 때문에, 시작 → 레버 + 레버 → 끝 지점을 나눠서 구해야한다.
◦
시간을 구하는 것은 BFS 로 진행하였다.
•
시간복잡도 :
•
성공 코드
추가된 좌표(new_x, new_y)는 미리 visit을 설정하는 것이 좋다.
queue에서 pop되기까지 visit 설정이 되지 않기 때문에, 다른 좌표를 탐색하며 중복으로 대상 좌표가 설정될 수 있다.
from collections import deque
def solution(maps):
def bfs(x, y):
queue = deque([(x, y, 0)])
# 레버까지의 최소 시간
to_lever_time = float('inf')
# 방문 여부 저장
visit = [[False] * len(maps[0]) for _ in range(len(maps))]
visit[y][x] = True
while queue:
x, y, time = queue.popleft()
if maps[y][x] == 'L':
to_lever_time = min(to_lever_time, time)
for move_x, move_y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
new_x = x + move_x
new_y = y + move_y
if 0 <= new_x < len(maps[0]) and 0 <= new_y < len(maps) and visit[new_y][new_x] == False and \
maps[new_y][new_x] != 'X':
queue.append((new_x, new_y, time + 1))
visit[new_y][new_x] = True
return to_lever_time if type(to_lever_time) != float else -1
for i in range(len(maps)):
for j in range(len(maps[0])):
if maps[i][j] == 'S':
start_to_lever = bfs(j, i)
if maps[i][j] == 'E':
end_to_lever = bfs(j, i)
return start_to_lever + end_to_lever if start_to_lever > 0 and end_to_lever > 0 else -1
Python
복사