[백준 14940번] 쉬운 최단거리 - java

문제 설명

1. 지도의 N과 M이 주어진다.

2. 가로세로(상하좌우)로 이동할 수 있고, 0은 못가는땅 1은 갈수있는땅 2는 목표지점이다.

3. 2에서 시작해서 도달 가능거리를 구한다.

4. 갈수있으면 도달까지 거리, 원래 갈수없으면 0, 원래 갈 수 있는데 못가면 -1을 출력한다.

 

풀이 과정

 1. BFS로 풀어나간다.

 2. 그냥 거리를 구하는것은 사실 간단하다. 기본적인 BFS를 사용해주면 된다.

 3. 문제 설명의 4번과정에 관해서 조금 생각을 해주어야 한다. 그리고 내 풀이보다 분명히 더 효율적인 방법이 있겠지만, 이렇게 해도 시간복잡도에 크게 문제될 것은 없어서 진행해 주었다.(코테의 시간복잡도에서는 안걸릴 방법이기 때문)

 4. 이를 생각하고 풀이과정을 도출해보자

---

A. 목표지점 2는 딱 한번 주어진다. 이를 Queue에 넣어준다.

B.  해당 장소로부터 움직이는 거리를 하나씩 더해가며 BFS를 해주면 쉽게 구해줄 수 있다.

C. 단, 갈 수 있는데 못가는곳은 -1이기 때문에 이동거리 저장용 배열은 시작할 때에 -1로 초기화해 준다.

D. 처음부터 못가는곳은 0이다. 마지막에 원래 못가는곳의 위치를 받아 0으로 변경해주면 된다.

---

코드