문제 1028 · 중급 5

가장 가까운 비상구

BFS · 격자 · 그래프 탐색

테스트별 제한 2000ms · 브라우저 채점

문제

화재 대피 훈련 날이다. 사무실 평면도가 R행 C열 격자로 주어진다. '.' 은 지나갈 수 있는 바닥, '#' 은 벽이나 책상, 'S' 는 지금 내가 있는 칸, 'E' 는 비상구다. 비상구는 하나 이상이다. 한 번에 위·아래·왼쪽·오른쪽으로 한 칸 움직일 수 있고 격자 밖으로는 나갈 수 없다. 가장 가까운 비상구까지 최소 몇 번 움직여야 하는지 구하라. 어느 비상구에도 갈 수 없으면 -1 을 출력한다. 'S' 와 'E' 칸도 지나갈 수 있다.

입력

첫째 줄에 R 과 C 가 주어진다. (1 ≤ R, C ≤ 300, R × C ≥ 2)

다음 R개 줄에 길이 C 인 문자열이 주어진다. 문자열은 . # S E 로만 이루어져 있고, S 는 정확히 하나, E 는 하나 이상 있다.

출력

최소 이동 횟수를 출력한다. 갈 수 없으면 -1 을 출력한다.

예제 입력 1

4 5
S..#E
.#.#.
.#...
...#E

예제 출력 1

예제 입력 2

2 3
S#E
.#.

예제 출력 2

-1

힌트 펼치기

너비 우선 탐색(BFS)은 가까운 칸부터 차례로 방문하므로, 처음 만나는 비상구까지의 거리가 곧 답이다.
Python 에서 큐는 collections.deque 를 쓰자. list.pop(0) 은 느리다.

풀이 작성

코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.