[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] 14888번: 연산자 끼워넣기  (0) 2018.01.15
[BOJ] 5397번: Keylogger  (0) 2018.01.15
[BOJ] 11723번: 집합  (0) 2018.01.13
  Comments
  • 바킹독님 잘보았습니다 ^^
    문제를 보자마자 떠오른 N*2*M*2 아이디어로 나는 천재야라고 생각하고 문제를 풀엇지만 역시나 시간 초과... N^4를 예상했지만 아이디어가 좋아 시도 했었지만
    바킹독님 아이디어에 일주일만에 고쳤네요. 막상 처음 떠올리기 어려운 아이디어로 생각합니다. 이런 아이디어는 경험치인가요? 아니면 또이 알고리즘 이름이 있는것인가요?
  • 오늘도 저의 부족함에 많이 배워 갑니다 ^^
  • 코딩몬
    어떻게 이런 아이디어를 생각을 하실 수 있는지 ㅠ 대단하십니다..
    강의 구독 잘 하고 있습니다, 항상 감사합니다 :)
댓글 쓰기