알고리즘 치즈(JAVA)

1840 : 치즈

제한시간: 1ms    메모리제한: 64MB
해결횟수: 601회    시도횟수: 1598회   

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색 으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모칸에 엑스친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

 

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치 즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어 가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후 에 녹아 없어져서 <그림 2>와 같이 된다.

 

 

 

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

 

 

 

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모 두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

 

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모 두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수 를 구하는 프로그램을 작성하시오.

 

입력 파일의 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다.
세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례 로 입력 파일의 둘째 줄부터 마지막 줄까지 주어진다.
치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어 지며 각 숫자 사이에는 빈칸이 하나씩 있다.

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출 력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

[Copy] 13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

[Copy] 3 5

?

?

1.  
2. /**************************************************************
3.     Problem: 1840
4.     User: a132034
5.     Language: Java
6.     Result: Success
7.     Time:277 ms
8.     Memory:12976 kb
9. ****************************************************************/
10.  
11.  
12. import java.util.LinkedList;
13. import java.util.Queue;
14. import java.util.Scanner;
15.  
16.  
17. public class Main
18. {
19.     private static Scanner sc;
20.     private static final int CHEESE = 1; //board를 위한 변수
21.     private static final int EMPTY = 0;  //board & visit을 위한 변수
22.     private static final int AIR = 1;    //label을 위한 변수
23.     private static final int VISIT = 1;  //visit을 위한 변수
24.     public static int [][] board;
25.     public static int [][] label;
26.     public static int [][] visit;
27.     public static int W,H;
28.     public static int remain;
29.     public static int count = 0;
30.     public static Queue<Point> queue = new LinkedList<Point>();
31.     public static Queue<Point> queueMelt = new LinkedList<Point>();
32.     public static void main(String[] args) {
33.         sc = new Scanner(System.in);
34.         //세로
35.         H = sc.nextInt();
36.         //가로
37.         W = sc.nextInt();
38.         board = new int[H][W];
39.         label = new int[H][W];
40.         visit = new int[H][W];
41.  
42.         for(int i = 0 ; i < H; ++i)
43.         {
44.             for(int j = 0 ; j < W; ++j)
45.             {
46.                 board[i][j] = sc.nextInt();
47.             }
48.         }
49.         queue.add(new Point(0,0));
50.         Labeling(queue);
51.         while(melting())
52.         {
53.             Labeling(queue);
54.             //카운트 증가
55.             count++;
56.         }
57.          
58.         System.out.println(count);
59.         System.out.println(remain);
60.     }
61.  
62.     public static void Labeling(Queue<Point> queue)
63.     {
64.         while(!queue.isEmpty())
65.         {
66.             Point pt = queue.remove();
67.  
68.             label[pt.x][pt.y] = AIR; //labeling(사실상 라벨은 공기가 있는 부분만 붙이면 됨..)
69.             visit[pt.x][pt.y] = VISIT; //방문함
70.              
71.              
72.             // 4 점을 모두 방문함.
73.             // > 쪽 점이 방문한 적 없고, 치즈가 아니며, 바운더리 내에 있을 때
74.             if(pt.y+1 < W && visit[pt.x][pt.y+1] == EMPTY && board[pt.x][pt.y+1] != CHEESE){
75.                 visit[pt.x][pt.y+1] = VISIT;
76.                 queue.add(new Point(pt.x, pt.y+1));
77.             }
78.                  
79.             // < 쪽 점이 방문한 적 없고, 치즈가 아니며, 바운더리 내에 있을 때
80.             if(pt.y-1 >= 0 && visit[pt.x][pt.y-1] == EMPTY && board[pt.x][pt.y-1] != CHEESE ){
81.                 visit[pt.x][pt.y-1] = VISIT;
82.                 queue.add(new Point(pt.x, pt.y-1));
83.             }
84.                  
85.             // ^ 쪽 점이 방문한 적 없고, 치즈가 아니며, 바운더리 내에 있을 때
86.             if(pt.x-1 >= 0 && visit[pt.x-1][pt.y] == EMPTY && board[pt.x-1][pt.y] != CHEESE ){
87.                 visit[pt.x-1][pt.y] = VISIT;
88.                 queue.add(new Point(pt.x-1, pt.y));
89.             }
90.                  
91.             // v 쪽 점이 방문한 적 없고, 치즈가 아니며, 바운더리 내에 있을 때
92.             if(pt.x+1 < H && visit[pt.x+1][pt.y] == EMPTY && board[pt.x+1][pt.y] != CHEESE ){
93.                 visit[pt.x+1][pt.y] = VISIT;
94.                 queue.add(new Point(pt.x+1, pt.y));
95.             }
96.              
97.         }      
98.     }
99.      
100.     public static boolean melting()
101.     {
102.         Queue<Point> tmpQueue = new LinkedList<Point>();
103.         Queue<Point> melt = new LinkedList<Point>();
104.         int re = 0;
105.          
106.         if(queueMelt.isEmpty())
107.         {
108.             for(int i = 0 ; i < board.length; ++i)
109.             {
110.                 for(int j = 0 ; j < board[0].length; ++j)
111.                 {
112.                     if(board[i][j] == CHEESE) //치즈일 경우
113.                     {
114.                         if(label[i][j+1] == AIR || label[i][j-1] == AIR || label[i+1][j] == AIR || label[i-1][j] == AIR ){
115.                             board[i][j] = EMPTY; //녹음 표시
116.                             tmpQueue.add(new Point(i,j));
117.                             queueMelt.add(new Point(i,j));
118.                             re++;
119.                              
120.                         }
121.                     }
122.                 }
123.             }
124.         }
125.         else
126.         {
127.             while(!queueMelt.isEmpty())
128.             {
129.                 Point pt = queue.remove();
130.                 int i = pt.x, j = pt.y;
131.                  
132.                 for(int ix = i-1; ix <= i+1; i+=2)
133.                 {
134.                     for(int jx = j-1; jx <= j+1; j+=2)
135.                     {
136.                         if(board[ix][jx] == CHEESE) //주변에 치즈가 있다면
137.                         {
138.                             board[ix][jx] = EMPTY; //녹음 표시
139.                             tmpQueue.add(new Point(ix,jx));
140.                             melt.add(new Point(ix,jx));
141.                             re++;
142.                         }
143.                     }
144.                 }
145.             }  
146.         }
147.         queueMelt = melt;
148.         queue = tmpQueue;
149.         if(re != 0){
150.             remain = re;
151.             return true;
152.         }
153.         else{
154.             //종료
155.             return false;
156.         }
157.     }
158.  
159.     public static class Point{
160.         public int x;
161.         public int y;
162.          
163.         Point(){
164.             x = 0; y = 0;
165.         }
166.         Point(int x, int y){
167.             this.x = x;
168.             this.y = y;
169.         }
170.          
171.     }
172. }

몇번 헤멨다. 그렇게 좋은 코드는 아닌 것 같지만.. 기본적으로 백트래킹 카테고리에 있었는데, 사실 백트래킹(dfs)은 자신이 없다. 

그래서 약간 다른 방법을 사용해서 풀었다. 

우선 final로 선언한 상수는... 사실 풀고나니 복잡한것 같기도 하고... 그냥 0 , 1 이렇게 써도 될 것 같기도 하다.. 큰 시스템이 아니니.. 

처음 동일한 크기의 2차원 배열을 3개 만들었다. 

방문 여부를 체크할 visit, 치즈를 입력받을 board, 바깥에 있는 공기인지 확인하기 위한 label

치즈는 정올 내에서 백트랙킹1 카테고리에 있지만... 다른 방법이 생각나서 label 배열을 만들었다.

풀이 방식은 

1. 바깥 공기를 골라낸다. (labeling) - 가장자리는 무조건 치즈가 없다고 헀으므로. 0,0은 바깥공기임이 확실하고 -> 이 점과 연결된 치즈가 아닌 점들은 모두 바깥공기일 것이다 -> queue에 집어넣어 너비우선탐색을 하여 label 배열을 만들어 준다. 

2. 녹는 과정 (melting) - 녹는 함수는 시간을 조금이라도 더 줄여보기 위해 큐를 하나 만들어서 처음 녹을 떄와 두번째 이상의 경우를 나뉘었다. 

1) 처음 녹일 경우 전체 label 배열을 체크하며 공기 주변에 치즈가 있는지 확인 한 후 -> 치즈가 있으면 치즈를 녹이고 치즈 자리를 큐에 추가해 준다. 

2) 두번째 부터는 큐에 이전에 치즈였지만 현재 녹아 공기가 된 위치가 들어있기 때문에 하나씩 큐에서 빼내어 확인하면 된다. 

이렇게 두가지 함수가 핵심이다. 

나머지는 자잘하기 때문에 사실 디버깅을 해 가며.. 하나씩 체크했던 것 같다. 

처음에는 문제 크기가 커질 경우 timeout이 되었는데, 이유는 라벨링 함수에서 사방을 확인할 때, 방문표시를 해주지 않으면 모든 점에서 사방을 확인하게 되어 탐색속도가 엄청나게 느려지기 때문이었다. 

이외에는 코드를 보면 어느정도 감이 잡힐 것이기 때문에... 자세한 설명은 생략한다.