BOJ 19045

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

 

코드

http://boj.kr/3abe2ed846844c988d8e303c5c2bc55f

 

Petrozavodsk Programming Camp Summer 2017 Day 2 C

 

난이도 : P1

 

Elapse Time : 40min

 

처음에는 '#'으로 되어 있는 부분을 BFS로 묶은 뒤 떨어지는 거리를 계산하려고 하였으나 예제처럼 블록 안에 블럭이 들어있는 경우에 떨어지는 칸 수를 계산하기 쉽지 않았다. 관찰을 해보니 특정 블럭이 떨어지는 칸수는 그 블럭의 열별 최하단 '#'과 그 바로 아래에 있는 '#'인 칸이 떨어지는 칸수와 그 칸과 블럭 사이에 있는 '.'의 개수에 영향을 받는다는 것을 알게 되었고 이는 다익스트라와 BFS를 적절히 섞어 사용하면 모든 칸의 떨어지는 칸수를 계산할 수 있다는 것을 뜻한다. 다익스트라와 BFS에서 중복된 칸을 계속해서 탐색하지 않도록 조절하여 시간 안에 통과할 수 있었다.