문제 설명
당신은 1 x 1 정사각형의 직사각형 그리드 형태로 미로에서 탈출하려고 합니다. 각 사각형은 통로 또는 벽으로 구성됩니다. 벽으로 둘러싸인 광장은 지나갈 수 없으며 복도로만 이동할 수 있습니다. 통로 중 하나에는 레버를 당겨야만 열 수 있는 미로 밖으로 나가는 문이 있습니다. 기어 중 하나에는 레버도 있습니다. 따라서 시작점에서 먼저 레버가 있는 셀로 이동하고 레버를 당긴 다음 미로에서 나가는 문이 있는 셀로 이동합니다. 아직 레버를 당기지 않았더라도 이 시점에서 출구가 있는 감방을 지나갈 수 있습니다. 미로에서 한 칸 이동하는 데 1초가 걸린다면 가능한 한 빨리 미로에서 빠져나오는 데 걸리는 시간을 찾고자 합니다.
미로를 매개변수로 나타내는 할당 문자열 배열이 주어지면 미로를 탈출하는 데 필요한 최소 시간을 반환하는 solve 함수를 완성합니다. 탈출할 수 없으면 -1을 반환하십시오.
제한
- 5 ≤ 카드 길이 ≤ 100
- 5 ≤ 카드 길이(i) ≤ 100
- maps(i)는 다음 5개의 문자로만 구성됩니다.
- S: 시작점
- E: 종료
- L: 레버
- 오: 갱
- 엑스: 벽
- 출발점과 출구, 지레는 항상 다른 곳에 있고 오직 하나만 있다.
- 출구는 레버를 사용하지 않고 사용할 수 있으며 모든 통로, 출구, 레버 및 시작 지점은 여러 번 사용할 수 있습니다.
I/O 예시
| 카드 | 결과 |
| (“수풀”, “XXXXO”, “OOOOO”, “OXXXX”, “OOOOE”) | 16 |
| (“LOOXS”,”OOOOX”,”OOOOO”,”OOOOO”,”EOOOO”) | -하나 |
I/O 예제 #1
'추천 관련글,
지정된 문자열은 미로와 같습니다.
가장 빠른 탈출 방법은 다음과 같이 이동하는 것입니다.
4번 이동하면 레버를 당기고 출구로 나가는데 총 16초가 걸린다. 따라서 16을 반환합니다.
설명
방법을 찾는 것은 전형적인 BFS 문제입니다.
다만, 중간에 통과해야 하는 지점(레버)이 있다는 점이 다릅니다. 따라서 BFS가 반환한 값을 방문하고 cnt 값 목록인 마지막 인덱스를 방문해야 합니다.
'''
통로로 된 칸(O) 나가려면 레버 필요
출발 지점(S) -> 레버(L)가 있는 칸 (레버 당긴 후) -> 미로 빠져 나옴(E)
레버 안 당겨도 출구 있는 칸 '지나갈 수' 있음
한 칸 이동 1초, 최대한 빠르게 미로를 빠져나가는 데 걸리는 시간은? (탈출 못하면 -1)
bfs
idea: *레버 어떻게 처리? => 레버로 가는 로직 + 레버에서 도착점으로
*cnt 어떻게 계산? => 별도의 리스트(visited) 사용
'''
from collections import deque
def solution(maps):
direction = ((0,1),(0,-1),(1,0),(-1,0))
n,m = len(maps),len(maps(0))
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
# 1. 어디가 시작인지 먼저 찾기
for i in range(n):
for j in range(m):
if maps(i)(j) == 'S':
sx,sy = i,j
# 레버 찾기
def bfs(x,y,end):
q = deque()
q.append((x,y))
visited = ((-1)*m for _ in range(n)) # (x,y)에서 출발해서 end로 갈 때 매번 경우에 따라 visit 갱신
visited(x)(y) = 0
while q:
x,y = q.popleft()
if maps(x)(y) == end:
return (visited(x)(y),x,y)
for i in range(4):
nx = x + dx(i)
ny = y + dy(i)
if 0 <= nx < n and 0 <= ny < m:
if visited(nx)(ny) == -1:
if maps(nx)(ny) != 'X': # 'O'인지 'L'인지 따질 필요 X
q.append((nx,ny))
visited(nx)(ny) = visited(x)(y) + 1
return None #end에 도달하지 못할 경우
answer = 0
cnt = bfs(sx,sy,'L')
if cnt == None:
return -1
answer += cnt(0) # answer 바로 선언하면 안됨
cnt = bfs(cnt(1),cnt(2),'E')
if cnt == None:
return -1
answer += cnt(0)
return answer
