https://www.acmicpc.net/problem/20947
요약
- 지도가 주어지고, 폭탄의 위치를 출력하면됨(답이 여러개임)
- 폭탄은 상/하/좌/우로 뻗어나가고, 충격파가 건물에 닿으면 건물 잔해가 됨
- 충격파는 건물/건물잔해에 닿으면 소멸됨
접근법
- 처음에는 어떻게 처리할지 막막했음
- 일단 절대 폭탄이 있어서는 안되는 위치를 찾는 접근을 해봄
- 있어도 되고 없어도 되면 폭탄이 있다고 해도 괜찮을 것 같음
- 충격파가 한쪽으로 뻗어나갔는데 건물이 나타난다? => 절대 폭탄이 그곳에 있으면 안됨
- 모든 위치에 대해서 일일이 확인한다면... n n n이 되어 시간초과발생
- 특정 행이나 열에 대해서, 한쪽 끝에서 탐색을 하면서
- 건물이 나왔다 => 이후에 폭탄이 있으면 안됨
- 잔해가 나왔다 => 상관없음
newbieski