728x90
😁 아이디어
1. BFS를 통해 최단거리를 찾는 방법을 2회에 걸쳐 진행한다.
2. 시작점 -> 레버, 레버 -> 끝점
3. 2회 동안 카운팅을 반환
😁 코드
from collections import deque
def solution(maps):
answer = 0
arr = []
sPos = []
ePos = []
lPos = []
width = len(maps[0])
height = len(maps)
for idx, m in enumerate(maps):
lst = list(m)
if 'S' in lst:
sPos = [idx, lst.index('S')]
if 'E' in lst:
ePos = [idx, lst.index('E')]
if 'L' in lst:
lPos = [idx, lst.index('L')]
arr.append(lst)
# start -> lever
lQ = deque([])
visit = [[0 for j in range(width)] for i in range(height)]
lQ.append([sPos[0], sPos[1], 0])
visit[sPos[0]][sPos[1]] = 1
getLMinTime = 10_000
while (lQ):
pos = lQ.popleft()
right = pos[1] + 1
if right < width and arr[pos[0]][right] != 'X' and visit[pos[0]][right] == 0 :
lQ.append([pos[0], right, pos[2] + 1])
visit[pos[0]][right] = 1
if right < width and arr[pos[0]][right] == 'L':
getLMinTime = pos[2] + 1
break
left = pos[1] - 1
if left >= 0 and arr[pos[0]][left] != 'X' and visit[pos[0]][left] == 0 :
lQ.append([pos[0], left, pos[2] + 1])
visit[pos[0]][left] = 1
if left >= 0 and arr[pos[0]][left] == 'L':
getLMinTime = pos[2] + 1
break
upper = pos[0] + 1
if upper < height and arr[upper][pos[1]] != 'X' and visit[upper][pos[1]] == 0 :
lQ.append([upper, pos[1], pos[2] + 1])
visit[upper][pos[1]] = 1
if upper < height and arr[upper][pos[1]] == 'L':
getLMinTime = pos[2] + 1
break
lower = pos[0] - 1
if lower >= 0 and arr[lower][pos[1]] != 'X' and visit[lower][pos[1]] == 0 :
lQ.append([lower, pos[1], pos[2] + 1])
visit[lower][pos[1]] = 1
if lower >= 0 and arr[lower][pos[1]] == 'L':
getLMinTime = pos[2] + 1
break
# lever -> end
eQ = deque([])
visit2 = [[0 for j in range(width)] for i in range(height)]
eQ.append([lPos[0], lPos[1], 0])
visit2[lPos[0]][lPos[1]] = 1
getEMinTime = 10_000
while (eQ):
pos = eQ.popleft()
right = pos[1] + 1
if right < width and arr[pos[0]][right] != 'X' and visit2[pos[0]][right] == 0 :
eQ.append([pos[0], right, pos[2] + 1])
visit2[pos[0]][right] = 1
if right < width and arr[pos[0]][right] == 'E':
getEMinTime = pos[2] + 1
break
left = pos[1] - 1
if left >= 0 and arr[pos[0]][left] != 'X' and visit2[pos[0]][left] == 0 :
eQ.append([pos[0], left, pos[2] + 1])
visit2[pos[0]][left] = 1
if left >= 0 and arr[pos[0]][left] == 'E':
getEMinTime = pos[2] + 1
break
upper = pos[0] + 1
if upper < height and arr[upper][pos[1]] != 'X' and visit2[upper][pos[1]] == 0 :
eQ.append([upper, pos[1], pos[2] + 1])
visit2[upper][pos[1]] = 1
if upper < height and arr[upper][pos[1]] == 'E':
getEMinTime = pos[2] + 1
break
lower = pos[0] - 1
if lower >= 0 and arr[lower][pos[1]] != 'X' and visit2[lower][pos[1]] == 0 :
eQ.append([lower, pos[1], pos[2] + 1])
visit[lower][pos[1]] = 1
if lower >= 0 and arr[lower][pos[1]] == 'E':
getEMinTime = pos[2] + 1
break
if getEMinTime == 10_000 or getLMinTime == 10_000:
return -1
else:
return getEMinTime + getLMinTime✔ 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/159993