[BOJ] 치즈

Posted on | In |

문제

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

제한사항

이외의 제한사항은 없다.

첫번째 생각

치즈 안쪽에 공기가 들어있을 수 있으므로,

우선 치즈가 녹는 공기(바깥공기)와 치즈가 녹지 않는 공기(안쪽공기)를 구분하고

바깥공기와 접촉한 치즈를 녹여가면서 구한다. 이 때, 남은 치즈의 갯수를 기록하고

치즈가 모두 녹았는지 체크를 한다. 치즈가 모두 녹았다면 남아있던 치즈의 갯수를 출력한다.

치즈가 모두 녹지 않았다면 남아있는 치즈의 갯수를 업데이트한다.

바깥공기 구하는 법

0,0에서 시작해서 BFS탐색을 통해 1이 아닌 모든 공간을 찾고, 이 과정을 통해 방문된 지점은 바깥공기이다.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static int col;
	static int row;
	static int count;
	static int ans;
	static int[][] map;
	static boolean[][] visit;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		col = sc.nextInt();
		row = sc.nextInt();
		count = 0; // 치즈의 갯수
		int countDay = 0;
		map = new int[col][row];
		visit = new boolean[col][row];
		for (int y = 0; y < col; y++) {
			for (int x = 0; x < row; x++) {
				map[y][x] = sc.nextInt();
				if ( map[y][x] == 1 ) {
					count++;
				}
			}
		}
		
		while( count > 0 ) { // 모든 치즈가 사라질때 까지 반복 
			countDay++;
			ans = count;
			findAir();
			melt();
		}
		
		System.out.println(countDay);
		System.out.println(ans);

	}
	

	public static void findAir() {
		// 치즈안에 있던 구멍이 바깥과 노출이 되었는가를 체크해야한다. 그렇기때문에 매번 BFS탐색을 한다.
		visit = new boolean[col][row];
		Queue<Point> q = new LinkedList<Point>();

		q.add(new Point(0,0));
		visit[0][0] = true;
		while(!q.isEmpty()) {
			Point p = q.poll();
			map[p.Y][p.X] = 2; 
			for(int dir=0; dir<4; dir++) {
				int tempX = p.X + dx[dir];
				int tempY = p.Y + dy[dir];
				if ( tempX >= 0 && tempY >= 0 && tempX < row && tempY < col ) {
					if ( (map[tempY][tempX] == 0 || map[tempY][tempX] == 2) && !visit[tempY][tempX] ) {
						visit[tempY][tempX] = true;
						map[tempY][tempX] = 2; 
						q.add(new Point(tempX,tempY));
					}
				}
			}
		}
	}
	
	public static void melt() {
		Queue<Point> turn = new LinkedList<>();
		for(int y=0; y<col; y++) {
			for(int x=0; x<row; x++) {
				if ( map[y][x] == 1 ) {
					for(int dir=0; dir<4; dir++) {
						int tempX = x + dx[dir];
						int tempY = y + dy[dir];
						if ( tempX >= 0 && tempY >= 0 && tempX < row && tempY < col ) {
							if ( map[tempY][tempX] == 2 ) { // 공기랑 접촉했다면
								turn.add(new Point(x,y));
								count--;
								break;
							}
						}
					}
				}
			}
		}
		// 이번 턴에 녹은 치즈들을 일괄적으로 처리해줌.
		while(!turn.isEmpty()) {
			Point p = turn.poll();
			map[p.Y][p.X] = 2; 
		}
	}
	
	
	public static class Point {
		int X;
		int Y;
		Point(int x,int y) {
			X=x;
			Y=y;
		}
	}
	
	
	public static void print() {
		for (int c = 0; c < col; c++) {
			for (int r = 0; r < row; r++) {
				System.out.print(map[c][r] + " ");
			}
			System.out.println();
		}
	}
}