목록2024/04/09 (1)
delpho
[골드3, BFS] 백준 2206 - 벽 부수고 이동하기 (자바)
Think 처음에는 벽 위치를 저장해두고, 하나씩 벽을 없애면서 모든 경우의 수를 dfs 했다. 그런데… 알고보니 시간복잡도가 NM^2였다. https://kscodebase.tistory.com/66를 참고했다. int[][][] isVisited를 활용하여, 벽을 뿌신 경우와 안뿌신 경우를 구분해서 관리할 수 있었다. DFS는 가중치가 없을 경우(다익스트라를 사용하지않아도 되는 경우), 무조건 최단거리를 보장한다. 또한, Queue 특성상, 벽을 뚫고 가는 경우와 안뚫고 돌아가는 경우 모두 체크가 가능하다 이 개념이 이 문제를 푸는 아이디어를 이해하는데에 중요한 포인트라고 생각한다 왜냐면…. 벽을 안 부수고도 현재 칸까지 도달이 가능하지만, 벽을 부수고 오는 것이 더 짧다고 가정해봅시다. 현재 지점에..
알고리즘/BFS, DFS
2024. 4. 9. 17:30