[BOJ] 백준 17267 상남자 (JAVA)

[BOJ] 백준 17267 상남자 (JAVA)Algorithm/- Baekjoon2024. 5. 14. 13:51@Koben

Table of Contents

📑 문제

BFS 응용문제, 다른 문제들과 비슷하게 상, 하, 좌, 우를 이동할 수 있지만 좌, 우는 이동 횟수가 제한된다.

그렇다면 총 이동할 수 있는 칸은 몇 칸인가? 를 물어보는 문제이다.

먼저 현재 좌표, 좌, 우 남은 이동 횟수를 담는 객체를 만들고 방문처리 및 0-1 BFS를 돌리면 된다고 생각했다.

하지만 91%쯤 실패한다... 예상컨대 큰 틀에서 구현자체는 틀리지 않았지만, 히든케이스를 만족시키지 못할 만큼

디테일하게 구현하지 못했던 것 같다

BFS 응용문제에선 대부분 방문처리에서 히든테스트케이스가 나온다.

기본적인 2차원 boolean 배열의 방문처리에는 한 가지 단점이 있다.

- 먼저 도착한 노드가 최적값인지, 아닌지를 판단하지 못하고 무조건 먼저 도착한 노드만 통과시킨다.

하나의 테스트 케이스를 가지고 예를 들어 보겠습니다.

파란색은 위로 탐색했을 때 가능한 범위, 주황색은 아래로 탐색했을 때 가능한 범위이다.

왼쪽으로 한 칸만 움직일 수 있는 경우, 파란색노드는 노란색칸을 탐색하지 못하지만, 주황색노드는 탐색가능하다. 하지만

파란색이 위치상 더 가깝기 때문에 노란색칸 바로 앞까지 먼저 방문하게 되고 이 경우 방문처리를 하게 되므로

결과적으론 주황색노드가 탐색가능한 칸을 막아버리는 경우가 생긴다.

주황색노드가 갈 수 있는 칸을 못 가게 해 버리는 상황이 발생한다. -> 초록색 체크 부분임

이 부분을 해결해야 히든테케를 통과 가능하다!

즉 다시 재방문할 때 이미 방문처리가 되어있어도, 이전 방문 때 남은 좌, 우 이동범위 합보다 현재 좌, 우 이동범위 합이 크다면

재방문하는 형식으로 구현해야 한다. (당연히 더 멀리 갈 가능성이 크니깐)

플레 5 문제치곤 쉬웠다. 히든테케 찾는 게 어려웠던 거 같다.. 구현자체는 깔끔하게 했다고 생각하는데 아마 더 좋은 방법이 있을 것 같다

한번 더 복습해야겠다 끝~~