저글링 방사능 오염 > 문제은행

본문 바로가기


알고리즘 BFS

1078 : 저글링 방사능 오염

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 1375 회    시도횟수: 4858 회   



승훈이는 심심한 시간에 스타크래프트(Starcraft) 게임을 하며 놀고 있었다. 스타크래프트 유닛중 하나인 저글링을 한 곳에 몰아세운 뒤, 방사능 오염 공격으로 없애보려고 했다. 그런데 좀 더 재미있게 게임을 하기 위해서 게임을 개조하여 방사능 오염 공격을 가하면 방사능은 1초마다 이웃한 저글링에 오염된다. 그리고 방사능에 오염된 저글링은 3초 후에 죽게 된다. 예를 들어 아래 왼쪽그림과 같이 모여 있는 저글링 중에 빨간 동그라미 표시를 한 저글링에게 방사능 오염공격을 가하면, 총 9초 후에 저글링들이 죽게 된다. 아래 오른쪽에 있는 그림의 숫자들은 각 저글링들이 죽는 시간이다.


efc6e5f9d670c6da62174cf11a66a8c2_1449814 
저글링을 모아놓은 지도의 크기와 지도상에 저글링들이 놓여 있는 격자 위치가 주어질 때, 총 몇 초 만에 저글링들을 모두 없앨 수 있는지 알아보는 프로그램을 작성하시오.

 


첫째 줄은 지도의 열의 크기와 행의 크기가 주어진다. 지도는 격자 구조로 이루어져 있으며 크기는 100×100칸을 넘지 않는다. 둘째 줄부터는 지도상에 저글링들이 놓여있는 상황이 주어진다. 1은 저글링이 있는 곳의 표시이고 0은 없는 곳이다. 마지막 줄에는 방사능오염을 가하는 위치가 열 번호 행 번호 순으로 주어진다.



죽을 수 있는 저글링들이 모두 죽을 때까지 몇 초가 걸리는지 첫 번째 줄에 출력하고 둘째 줄에는 죽지 않고 남아 있게 되는 저글링의 수를 출력하시오.


[Copy]
7 8 
0010000 
0011000 
0001100 
1011111 
1111011 
0011100 
0011100 
0001000
3 5
[Copy]
9
0



HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.