알고리즘 저글링 방사능 오염(JAVA)

1078 : 저글링 방사능 오염

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 697회    시도횟수: 2725회   

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

 

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

 

 

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

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

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

[Copy] 9 0

1. import java.util.LinkedList;
2. import java.util.Queue;
3. import java.util.Scanner;
4.  
5. public class Main {
6. @SuppressWarnings("resource")
7. public static void main(String[] args) {
8. Queue<Point> queue = new LinkedList<Point>();
9. int[][] map = null;
10. Scanner sc = new Scanner(System.in);
11. int x = sc.nextInt();
12. int y = sc.nextInt();
13. map = new int[y][x];
14.  
15. char[] tmp = null;
16. //입력이 붙어서 들어오기 때문에 문자열로 받아서 각각 숫자로 저장.
17. sc.nextLine();
18. for (int i = 0; i < map.length; i++) {
19. tmp = sc.nextLine().toCharArray();
20. for (int j = 0; j < map[i].length; j++) {
21. map[i][j] = tmp[j] - '0';
22. }
23. }
24.  
25. //시작위치 입력
26. int stY = sc.nextInt() - 1;
27. int stX = sc.nextInt() - 1;
28.  
29. //queue에 연산할 위치(시작위치) 삽입
30. queue.add(new Point(stX, stY));
31.  
32. //시작위치는 3초후 죽음.
33. map[stX][stY] = 3;
34. int count = 3;
35. //죽는시간 체크
36.  
37. // 감염시킬게 없을 때 까지(queue에 더이상 연산 할 게 없을 떄 까지)
38. while(!queue.isEmpty())
39. {
40. count++;
41. bfs(map, queue, count);
42. }
43.  
44. // 살아남은 저글링수 계산
45. int aliveCount = 0;
46. for (int i = 0; i < map.length; i++) {
47. for (int j = 0; j < map[0].length; j++) {
48. if(map[i][j] == 1){
49. aliveCount++;
50. }
51. }
52. }
53.  
54. System.out.println(--count);
55. System.out.println(aliveCount);
56. }
57.  
58. //bfs
59. private static void bfs(int[][] map, Queue<Point> q,
60. int count) {
61. Point a = null;
62. int size = q.size();
63.  
64. for(int len = 0 ; len < size; ++len)
65. {
66. a = q.remove();
67. if(a.x-1 >= 0)
68. {
69. if(map[a.x - 1][a.y]== 1)
70. {
71. map[a.x - 1][a.y] = count;
72. q.add(new Point(a.x-1, a.y));
73. }
74. }
75.  
76. if(a.x+1 < map.length)
77. {
78. if(map[a.x + 1][a.y]== 1)
79. {
80. map[a.x + 1][a.y] = count;
81. q.add(new Point(a.x+1, a.y));
82. }
83. }
84.  
85. if(a.y-1 >= 0)
86. {
87. if(map[a.x][a.y-1] == 1)
88. {
89. map[a.x][a.y-1] = count;
90. q.add(new Point(a.x,a.y-1));
91. }
92. }
93.  
94. if(a.y+1 < map[0].length)
95. {
96. if(map[a.x][a.y+1] == 1)
97. {
98. map[a.x][a.y+1] = count;
99. q.add(new Point(a.x,a.y+1));
100. }
101. }
102. }
103. }
104. }
105.  
106. class Point {
107. public int x;
108. public int y;
109.  
110. public Point(int x, int y) {
111. this.x = x;
112. this.y = y;
113. }
114. }

이상하게 복사가 되서 탭이 적용이 안됬다.. 이클립스라면 ctrl+a로 전체 선택 후 ctrl+i로 자동 indent를 적용하면 보기 쉬울 것.

너비 우선 탐색(bfs)문제의 기본 문제라고 할 수 있다. 

보통 bfs의 경우 queue를 사용해 풀면 쉽게 풀 수 있다.

시작점이 주어지고(queue에 삽입), 주어진 점(queue에서 꺼냄) 더이상 감염될 수 없을 때 까지 반복하여 4방향(위, 아래, 왼쪽, 오른쪽)으로 감염을 시도한다. 

이때 저글링이 없거나(0) 바운더리라면 감염하지 않으며, 저글링이 있는 경우 저글링이 죽을 시간을 그 위치에 설정해준다(count변수) 

이 저글링은 다시 queue로 삽입해준다.(새로운 시작점이 된다.)

반복하여 queue에 아무 저글링의 위치도 들어와있지 않을 때 함수는 종료되며 

map(저글링이 죽는 시간이 써있는 2차원 배열)에 각 저글링이 몇 초에 죽는지 등록되고 이 시간이 등록되지 않은 저글링(1로 남아있는 저글링)이 살아있는 저글링이다.