Search

미로탈출

문제 설명 : 레버가 존재하는 미로의 탈출 최소 시간을 구한다.
풀이 방법
반드시 레버를 거쳐야하기 때문에, 시작 → 레버 + 레버 → 끝 지점을 나눠서 구해야한다.
시간을 구하는 것은 BFS 로 진행하였다.
시간복잡도 : O(NM)O(N * M)
성공 코드
추가된 좌표(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
복사