목록백준 2206번 (1)

kakasoo

[bfs] 벽 부수고 이동하기 (백준 2206번)

질문에 있는 글인데, 너무나 잘 정리되어 있어서 가지고 왔다. (*이런 것에는 저작권이 없겠지?) 1. 가중치가 없는 최단 경로, 한 마디로 다익스트라 알고리즘을 써야 하는 게 아니면 무조건 bfs라는 것. 2. 모든 칸을 0으로 하나씩 바꿔보는 브루트 포스는, 최악의 경우 (1000 * 1000)^2의 반복이 된다. (map size = 1000 * 1000, 이고 각각의 칸이 모두 1인 경우가 있을 수 있기 때문에 1000000000000 번이다.) 3. 칸마다 방문 체크를 하는 방식으로는 풀 수 없다. 이거 참 중요한 이야기인데, 벽을 부수지 않은 세계와 벽을 부순 적 있는 세계가 있다고 가정해보자. 벽을 부수지 않은 세계를 0번 세계, 그리고 부순 세계를 1번 세계라고 할 때, 0번 세계에서 0번..
프로그래밍/알고리즘 풀이 2020. 3. 3. 22:36
이전 Prev 1 Next 다음