[BOJ] 백준 17836 공주님을 구해라! (JAVA)

[BOJ] 백준 17836 공주님을 구해라! (JAVA)Algorithm/- Baekjoon2024. 2. 13. 19:53@Koben

Table of Contents

📑 문제

"검을 먹는 경우"와 "검을 먹지 않는 경우"를 구하고 제한시간에 맞는 경우를 출력하자.

기본적인 BFS 알고리즘을 사용하지만 검을 먹는 경우 or 검을 먹지 않는 경우를 분리해서 풀어야 한다.

그러기 위해선 BFS 알고리즘을 실행해서 검을 먹을 수 있는지에 대한 여부를 확인하고 먹었다면

먹은 위치에서 목표가 있는 위치까지 벽을 부술 수 있기 때문에(장애물이 없다) 맨해튼 거리 로 최단 거리를 구해 더해주면 된다.

Way1, Way2 는 도착할 수 없는 경우도 있기 때문에 Max 값으로 설정 후 진행한다

Way1 = 검을 먹지 않는 경우 -> 기본 BFS으로 목적지까지 소요시간

Way2 = 검을 먹은 경우 -> 검을 먹기까지 소요시간 + 맨해튼거리(한 칸 당 한 시간)

검을 먹기만 한다면 무조건 목적지에 도착하기 때문에 검 획득 여부가 중요하다

맨해튼 거리 공식 = (x1 - x2) + (y1 - y2), 장애물이 없다면(무시 가능하다면) BFS를 다시 실행할 필요 없이 공식 만으로

최단거리를 구할 수 있다!

bfs() = BFS 알고리즘, 검 획득여부를 boolean형으로 반환한다.

즉, 검을 먹지 못했다면 Way2는 고려할 필요가 없다. 하지만 검을 먹었다면 검까지 걸린 시간 + 목적지까지 맨해튼거리를

구하면 된다.

다른 유저가 작성한 정답 코드를 봤는데 다들 bfs 알고리즘에 검 획득 여부에 따라 다르게 작동하게 구현했다

이런 방법도 생각했지만 복잡해질 수 있을 것 같아서 나름대로 논리를 단순화시켜 보았다 ㅎㅎ

내가 직접 생각해 내서 그런지 나에겐 쉽게 와닿았는데 다른 사람들도 공감할지 궁금하다^^