[BOJ] 2206번: 벽 부수고 이동하기

https://www.acmicpc.net/problem/2206


모든 벽에 대해, 그 벽을 부수고 DFS를 수행하는 방식으로 처리한다면 시간복잡도는 O(N^2M^2)으로 시간 내에 해결이 어렵습니다. 대신 아래와 같은 아이디어로 시간복잡도를 O(NM)으로 만들 수 있습니다. (참고로 저는 인덱스를 (0, 0) to (N-1, M-1)로 뒀습니다.)


최단거리는


i)  벽을 파괴하지 않고 (0, 0)에서 (N-1, M-1)까지 가는 거리이거나


ii) 임의의 벽에 대해, 그 벽과 인접한 4개의 칸 중에서 (0,0)과 가장 가까운 것의 거리 + 인접한 4개의 칸 중에서 (N-1,M-1)과 가장 가까운 것의 거리  + 1 중 하나입니다.


i)은 자명하게 O(NM)에 구할 수 있고 ii) 또한 미리 모든 방문 가능한 칸에 대해 (0, 0)과의 거리와 (N-1, M-1)과의 거리를 계산해두면 O(NM)에 구할 수 있습니다.


https://github.com/blisstoner/BOJ/blob/master/2206.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11559번: Puyo Puyo  (0) 2018.01.16
[BOJ] 1072번: 게임  (0) 2018.01.15
[BOJ] 2217번: 로프  (0) 2018.01.15
[BOJ] 2206번: 벽 부수고 이동하기  (5) 2018.01.15
[BOJ] 14888번: 연산자 끼워넣기  (0) 2018.01.15
[BOJ] 5397번: Keylogger  (0) 2018.01.15
[BOJ] 11723번: 집합  (0) 2018.01.13
  Comments
댓글 쓰기