문제이해
스타트출발->레버당기고->출구로 나가기위한 최소시간구하기(한칸1초) 못나가면 -1
통로로만이동가능하며 통로는 O 벽은 X 로 표현됨
참고<백준 미로탈출>
def bfs(i,j):
while queue:
i,j = queue.pop(0)
if i == N-1 and j == M-1:
return visited[i][j]
for d in range(4):
ni = i + di[d]
nj = j + dj[d]
if 0<= ni < N and 0<= nj <M and miro[ni][nj] and visited[ni][nj] == 0:
queue.append((ni,nj))
visited[ni][nj] = visited[i][j] + 1
di = [-1,0,1,0]
dj = [0,1,0,-1]
N,M = map(int,input().split())
miro = [list(map(int,input())) for _ in range(N)]
visited = [[0]* M for _ in range(N)]
queue = [(0,0)]
visited[0][0] = 1
print(bfs(0,0)) # 시작점 (1,1)이니까 (0,0)
1. 시작점찾고 출발하기 시작점못찾으면 return -1
2. 시작위치에서 bfs돌리기 : 목적지 : 'L' (시작x좌표,시작y좌표, 우리의목적지, maps) -> 걸리는시간 return
3. 위에서 못찾으면 return -1
4. 레버찾은 위치에서 bfs돌리기 : 목적지 : 'E'
5. 못팢으면 return -1
di = [-1,0,1,0]
dj = [0,1,0,-1]
def bfs(start,end,target,maps):
n, m = len(maps), len(maps[0])
queue = [(start,end,0)]
visited = [[False]*m for _ in range(n)]
visited[start][end] = True
while queue:
i,j,second = queue.pop(0)
if maps[i][j] == target:
return i,j,second
for d in range(4):
ni = i + di[d]
nj = j + dj[d]
if 0<=ni<n and 0<=nj<m and not visited[ni][nj] and maps[ni][nj] != 'X':
queue.append((ni,nj,second+1))
visited[ni][nj] = True
return -1,-1,-1
def solution(maps):
n,m = len(maps),len(maps[0]) # maps의 행과 열의 수
s = -1
for i in range(n):
for j in range(m):
if maps[i][j] == 'S': # 출발점 찾기
s,e = i , j
if s == -1: # 츨발점을 찾지못함
return -1
# 레버찾기
lever_x,lever_y,time_lever = bfs(s,e,'L',maps)
if time_lever == -1: # 레버를 못찾음
return -1
end_x,end_y,time_end = bfs(lever_x,lever_y,'E',maps)
if time_end == -1: # 도착지를 못찾음
return -1
return time_end+time_lever
maps = ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]
print(solution(maps))
