[백준 06593] 상범 빌딩 [Java]

문제

https://www.acmicpc.net/problem/6593

---

풀이

L, R, C로 이루어진 직육면체에서 상하좌우, 위, 아래로만 이동하며 출발지 S에서 도착지 E로 도착하는데 걸리는 최단 시간을 구하는 문제다.

BFS를 3차원으로 확장하면 되는 기본 문제다.

우선 시작 전 문자나 상태를 정의해주자.

상위 그래프 문제로 갈수록 이처럼 문제에서 주어지는 문자들을 자신의 언어로 변환해주는게 실수를 방지하는데 도움이 된다.

L, R, C가 모두 0이 아닐 때 까지 입력을 받으며 탐색을 진행하면 된다.

그래프 정보를 입력받으며 벽을 표시해주고, 시작점과 종료점의 위치를 파악해주자.(sl, sr, sc, el, er, ec)

각 층마다 한 줄 공백 입력이 주어진다는 점에 유의하자.

기본 BFS를 3차원으로 확장해 구현해주면 된다.

단, 도착지까지 빠져나오는데 걸리는 최소시간을 기록해야 하므로 다음 정점을 큐에 담아줄 때 방문 여부를 기록하는 배열( visited )에는 현재 정점까지 소모된 시간( board[cur[0]][cur[1]][cur[2]] )에 1초를 더해 기록해주자.

방문하지 않은 지역은 0, 벽은 -1이다.

방문하지 않은 지역과 겹치지 않도록 부득이하게 출발 지점 S의 소요 시간을 1로 초기화해주었다.

이 부분을 고려해 만약 다음 정점이 도착 지점 E라면 1초를 더하지 않고 정답을 반환해주자.

만약 모든 정점을 탐색했음에도 E에 도달하지 못한다면 -1를 반환해주자.

bfs가 반환환 시간에 따라 정답을 출력하면 된다.

---

소스코드

보기