미로 탈출
Programmers
1. 문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.
미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.
2. 제한 사항
5 ≤ maps의 길이 ≤ 100
- 5 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
S : 시작 지점
E : 출구
L : 레버
O : 통로
X : 벽- 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.
3. 너비우선탐색(BFS) 알고리즘
- 정의
- 임의의 노드를 시작으로 인접한 노드를 우선적으로 탐색하는 알고리즘
- 시작 지점에서 가까운 곳부터 탐색을 시작하고, 먼 곳은 나중에 방문하는 순회 기법 중 하나
- 두 노드 사이의 최단 경로나, 임의의 조건이 부여된 경로를 찾는 데 용이함.
- 사용
- 기본적으로 노드를 방문하면서, 나오는 경우의 수를 고려하고, 가까운 노드부터 선입선출형식과 같이 시행하기 위해 자료구조형 Queue를 사용하는 편이다.
- 본 사례는 특별하게 시작지점에서 레버로, 레버에서 종료지점으로 두가지 경우기 때문에 작성의 편의성상 재귀함수를 사용하였지만, 한가지 경로를 탐색하는 경우에는 재귀함수를 사용하지 않고 탐색이 가능.
- DFS와 마찬가지로 경로를 탐색함에 있어서 Visit 배열 (방문여부)을 설정하고 저장할 필요성이 있음. <그렇지 않으면 무한 루프에 빠질 가능성이 있다.>
- 기본적으로 "노드 방문 -> 해당 노드와 연결된(인접한) 노드들을 모두 Queue에 저장 -> Queue에서 하나의 좌표를 꺼내와(deque.popleft(),등을 통해) 이동" 을 모든 Queue(방문할 곳)가 소진될 때 까지 반복한다.
4. 작성 코드
# 전역 변수로 이동할 방향 설정
dx=[0,1,0,-1]
dy=[1,0,-1,0]
# sys라이브러리 호출 및 setrecursionlimit() : 재귀함수 호출 제한횟수를 늘려줌
import sys
sys.setrecursionlimit(10**8)
# BFS를 위한 deque 자료 구조형 호출
from collections import deque
# BFS
def bfs(maps,visit,width,height,x,y):
queue=deque() # queue를 deque자료 구조형으로 선언
queue.append((x,y)) # 시작 좌표를 넣고
while queue:
a,b=queue.popleft() # a와 b의 값을 받아
for i in range(4):
# 상 하 좌 우 방향으로 이동을 하는데,
ddx=a+dx[i]
ddy=b+dy[i]
# 범위에서 벗어나면 넘어가고,
if ddx>=width or ddy>=height or ddx<0 or ddy<0:
continue
# 이미 들렸던 곳이라면 넘어가고,
if visit[ddy][ddx]!=0:
continue
# 갈 수 없는 곳이면 넘어가고,
if maps[ddy][ddx]=="X":
continue
# 아니라면 이전 좌표의 1을 더한 지점을 현재 좌표로 지정하고,
visit[ddy][ddx]=visit[b][a]+1
# queue에 append하여, 이동한 좌표에서 반복한다.
queue.append((ddx,ddy))
def solution(maps):
answer = 0
width=len(maps[0]) # 가로 길이
height=len(maps) # 세로 길이
visit=[[0]*width for i in range(height)] # BFS(DFS도 사용함)를 위한 방문함수
for i in range(height):
for j in range(width):
if maps[i][j]=="S":
s=(i,j) # start 좌표 찾기
if maps[i][j]=="E":
e=(i,j) # end 좌표 찾기
if maps[i][j]=="L":
l=(i,j) # 레버 좌표 찾기
visit[s[0]][s[1]]=1 # start의 좌표를 방문함을 표시함
x=s[1] # 현재 x좌표
y=s[0] # 현재 y좌표
bfs(maps,visit,width,height,x,y) # 입력받은 값을 통해서, 시작지점 좌표에서 BFS수행
if visit[l[0]][l[1]]: # 레버 좌표를 갈 수 있다면 ans1에 그 시간을 저장
ans1=visit[l[0]][l[1]]
else: # 레버도 도달할 수 없다면 -1 리턴
return -1
visit=[[0]*width for i in range(height)] # 방문 함수를 다시 초기화
x=l[1]
y=l[0]
bfs(maps,visit,width,height,x,y) # 레버 지점에서 도착 지점까지 BFS를 수행
if visit[e[0]][e[1]]: # 만약에 도착할 수 있다면, 앞의 ans1값과 더하고 -1(시작 방문을 1로 설정되어있기 때문.)
return visit[e[0]][e[1]]+ans1-1
else: # end지점에 갈 수 없으면 -1 return
return -1
I'm Free!