Algorithm
-
BOJ - 2206 벽부수고 이동하기PS 2024. 7. 6. 10:18
https://www.acmicpc.net/problem/2206경로구하기 문제이다.우선 최단경로를 구하는 거기 때문에 bfs를 생각해 볼 수 있다.이제 벽을 뚫는 걸 생각해야 하는데,처음 생각했을때, 벽을 하나씩 부수는 경우의 수를 생각해봤다.그런데, 문제의 조건에서 n 벽을 하나씩 부순다면 1000 * 1000 = 100만 을 기본으로 깔고탐색 1000 * 1000 = 100만. 100만 * 100만 이라는 말도 안되는 시간복잡도가 나오기 때문에 다른 방법을 생각해보기로 했다.두번째로 생각한 방법은 벽을 만날때 이걸 뚫고 가고, 이 뚫는 횟수를 1번까지만 허용하는 거다.그래서 보통 큐에 y좌표, x좌표만 저장하는데 거기다가 추가로 지금까지 벽을 몇개 뚫었나도 저장했다.그리고 1번까지만 벽을 뚫을 수 ..