프로그래머스 미로 탈출 C++

 

 

직사각형 격자 형태의 미로에서 탈출할려고 한다.

각 칸은 통로 또는 벽으로 구성되어있으며, 통로 어딘가에는 탈출구의 문을 열 수 있는 레버가 있다.

먼저 레버를 찾아 당겨 미로를 빠져나갈 수있는 문을 열고

해당 문으로 이동하여 탈출하는 문제이다.

 

한칸 이동 시에는 1초가 걸린다고 할때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구해라

 

미로는 S : 시작,  E : 출구, L : 레버. O : 통로, X : 벽 으로 이루어진 문자로 구성되어있다.

 

최단 경로를 찾는 문제로

L 레버 까지의 최단 거리를 찾고

레버부터 E 출구 까지의 최단 거리를 찾아

두값을 더하면 최대한 빠르게 나갈 수 있는 길이 나오게 된다.

 

BFS를 이용