창영이와의 퇴근
-
[백준]22116: 창영이와의 퇴근 - JAVA문제풀이/백준 2021. 7. 21. 14:56
[백준]22116: 창영이와의 퇴근 풀이 🪑 단순 BFS라고 착각할 수 있으나 BFS는 거들 뿐,, 핵심 로직은 이분탐색을 사용해야 하는 문제이다! 📝 문제를 정리해 보자! 1, 1 -> N, N으로 이동한다. (나는 편의를 위해 0, 0 -> N-1, N-1로 생각해 주었다.) 상, 하, 좌, 우로 한 칸씩 이동한다. 인접 격자 사이의 높이차를 경사라고 할 때 지날 수 있는 최대 경사의 최솟값을 구한다. 📌 최대 경사의 최솟값! 이런 문제 유형은 이분탐색 유형이다. 바로 이분탐색으로 풀어야 겠다고 생각했다. 문제 조건에서 경사 높이의 범위를 보면, 1 에서 1000000000사이인걸 알 수 있다. 이 범위의 값을 이분탐색 해 준다. 🔧 문제 구현 과정을 생각해 보자. 격자의 정보를 입력 받는다. 구해야..