[백준 23352번] 방탈출 - java

문제 설명

1. NxM크기의 격자판이 주어진다.

2. 상하좌우로 움직일 수 있으며, 각 방의 이동은 최단 경로로 움직인다.

3. 이렇게 최단 경로로 움직여서 가장 먼 거리를 움직이면, 그 시작점과 도착점이 비밀번호가 된다.

4. 가장 먼 거리가 여러개면 그 중 시작점과 도착점의 합이 큰 것이 비밀번호가 된다.

 

풀이 과정

 1. 최단 경로 -> BFS 그냥 공식처럼 외워서 진행하자. 

 2. 우리는 어디서부터 시작하는게 최고로 가까울지 모른다. 그러므로 모든 점에 대해 그곳부터 시작하는 경우를 싹 다 구해야 할 것이다. 

이 말은 완전탐색 + BFS로 진행해야 한다는 것이다.

 3. BFS를 통해 나아가면서, 해당 위치가 마지막인지 어떤지 모르므로 매번 거리를 재서 진행하는것이 속편할 것이다. 이는 BFS여서 쉽게 구할 수 있다.

 4. 알고리즘을 구현하면 다음과 같다.

A) 모든 점에 대해서 0이 아니면 해당 위치를 시작점으로 잡고 BFS시작 -> 당연히 이 모든 점에 대해서 BFS를 시작하기 전에 boolean을 초기화해주고, 해당 위치만 방문표시 해 줄 것이다.

B) 이동하면서 현재 이동거리가 최대 이동거리보다 많으면 그 최대 이동거리를 변경해주고, 현재위치가 도착점으로 판단해서 시작점+도착점을 ans로 저장해주면서 쭉쭉 이동한다.

C) 그리고 다시 상하좌우에서 갈 수 있는지 판단하여 이동하고 위의 내용을 다시 해주면 된다!!

 5. 난이도가 매우 높은 문제는 아니다. 다만 고려해야 할 사항이 함정처럼 있다....주의할것.

 6. 그리고 한가지 중요한것!! 방문체크는 상화좌우 판단시기에 해주자!! 아니면 큰일난다!!!

이건 매우 과장된 예시이긴 하지만... 이런 식으로 하나의 점에 대해 여러 Queue의 값에서 확인하고, 확인하고, 또 확인하는 코드가 돌아가게 된다.

이는 메모리 초과의 원인이 된다!!!!!

이렇게 강조하는 이유는 내가 실제로 그 메모리 초과에서 헤맸기 때문이다.

코드