[BaekJoon] 2636 치즈

1.  문제 링크

https://www.acmicpc.net/problem/2636

2.  문제

요약

• 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈가 놓여집니다.
• 판의 가장자리에는 치즈가 놓여질 수 없고 치즈에는 하나 이상의 구멍이 있을 수 있습니다.
• 치즈가 놓여져 있는 칸에서 치즈는 공기와 접촉된 후 한 시간이 지나면 녹아 없어집니다.
• 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여있는 칸의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 100보다 작거나 같은 양의 정수인 세로와 가로의 길이가 주어지고 두 번째 줄부터 마지막 줄까지 판의 각 가로줄의 모양이 윗 줄부터 차례대로 주어집니다.
  • 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어집니다.
• 출력: 첫 번째 줄에 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고 두 번째 줄에 모두 녹기 한 시간 전에 남아있는 치즈 조각이 놓여있는 칸의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	static int row, col;
	static int[][] map;
	boolean[][] visited;
	static int count;
	int[] dx = {-1, 0, 1, 0};
	int[] dy = {0, -1, 0, 1};
	public void dfs(int x, int y) {
		for(int i = 0; i < 4; i++) {
			int cx = x + dx[i];
			int cy = y + dy[i];
			if(cx >= 0 && cx < row && cy >= 0 && cy < col) {
				if(!visited[cx][cy]) {
					visited[cx][cy] = true;
					if(map[cx][cy] == 1) {
						map[cx][cy] = 2;
						count++;
					} else {
						dfs(cx, cy);
					}
				}
			}
		}
	}
	
	public boolean findEdge() {
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				if(map[i][j] == 2) {
					map[i][j] = 0;
				}
			}
		}
		for(int i = 0; i < row; i++) {
			for(int j = 0; j < col; j++) {
				if(map[i][j] == 1) {
					return true;
				}
			}
		}
		return false;
	}
	
	public int getHourAndCheese() {
		visited = new boolean[row][col];
		int result;
		for(result = 0; findEdge(); result++) {
			for(boolean[] v : visited) {
				Arrays.fill(v, false);
			}
			visited[0][0] = true;
			count = 0;
			dfs(0, 0);
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		row = Integer.parseInt(input[0]);
		col = Integer.parseInt(input[1]);
		map = new int[row][col];
		for(int i = 0; i < row; i++) {
			input = br.readLine().split(" ");
			for(int j = 0; j < col; j++) {
				map[i][j] = Integer.parseInt(input[j]);
			}
		}
		br.close();
		Main m = new Main();
		bw.write(m.getHourAndCheese() + "\n" + count + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DFS를 이용하여 해결할 수 있습니다.
• 각 시간마다 판 위에 치즈가 존재하는지 확인하고 만약 아직 존재한다면 공기와 맞닿는 치즈를 찾습니다.
• 1시간 뒤에 녹아서 사라질 치즈에 대해 판에서 해당 위치의 값을 2라고 정하고 진행하였습니다.
• 치즈가 판에 아직 남아있는지 확인할 때에는 모든 판을 돌면서 값이 2인 부분은 치즈가 사라져야하므로 해당 값을 0으로 변경합니다.
• 값을 변경해준 후에 판의 모든 부분을 확인하면서 아직 값이 1인 부분, 즉 치즈가 있는 부분이 있는지 확인하고 만약 있다면 판에 치즈가 남아있으므로 true를 반환하고 그렇지 않다면 false를 반환합니다.
• 만약 각 시간에서 치즈가 판에 아직 남아있다면 공기와 맞닿은 치즈들을 찾아야 합니다. 이 때는 DFS를 이용하여 구합니다.
• (0, 0)부터 시작하여, 즉 공기를 기준으로 탐색하고자 하는 위치의 상하좌우 칸들을 확인하면서 공기와 맞닿아있는 치즈를 찾고 해당 위치의 값을 2로 변경해줍니다.

public void dfs(int x, int y) {
	for(int i = 0; i < 4; i++) {
		int cx = x + dx[i];
		int cy = y + dy[i];
		if(cx >= 0 && cx < row && cy >= 0 && cy < col) {
			if(!visited[cx][cy]) {
				visited[cx][cy] = true;
				if(map[cx][cy] == 1) {
					map[cx][cy] = 2;
					count++;
				} else {
					dfs(cx, cy);
				}
			}
		}
	}
}

1. 주어진 판의 값을 2차원 배열 map에 설정하고 DFS 진행 시에 해당 칸을 방문하였는지 나타내는 map과 같은 크기의 2차원 배열 visited를 생성합니다. 또한 치즈가 모두 녹아서 사라질 때의 시간을 설정하기 위해 변수 result를 생성합니다.
2. 0시간부터 판에 더 이상 치즈가 없을 때까지 시간을 1시간씩 증가시키면서 공기와 맞닿는 치즈들을 찾고 시간이 지남에 따라 녹은 치즈를 판에서 없애며 판에 치즈가 없을 때의 시간을 찾습니다.
   1. 판에 치즈가 남아있는 확인할 때에는 판의 모든 칸들을 돌면서 해당 칸의 값이 2라면 1시간 뒤에 녹을 치즈라는 의미이므로 해당 값을 0으로 변경해줍니다.
   2. 값을 변경해준 후에 모든 칸을 돌면서 치즈가 남아있는지, 즉 판의 값이 1인 곳이 남아있는지 확인하고 아직 남아있다면 true를 반환하고 그렇지 않다면 false를 반환하여 반복문을 끝냅니다.
   3. 만약 아직 판에 치즈가 남아있다면 visited의 값을 DFS를 실행하기 전에 방문하지 않았다는 의미로 모두 false로 초기화합니다.
   4. (0, 0)부터 DFS를 실행할 것이기 때문에 (0, 0)의 visited 값을 true로 변경하고 판에 치즈가 없는 시간의 1시간 전에 판에 남아있는 치즈의 개수를 나타내는 변수 count의 값을 0으로 초기화합니다.
   5. (0, 0)부터 시작하여 DFS를 통해 공기와 맞닿은 치즈들을 찾습니다.
      1. 탐색하려는 칸의 상하좌우 칸을 각각 확인하는데, 만약 해당 칸이 판에 존재하고 아직 방문되지 않았다면 해당 칸을 방문할 것이기 때문에 해당 칸의 visited 값을 true로 변경해줍니다.
      2. 해당 칸의 값이 1이라면, 즉 치즈가 있는 칸이라면 해당 칸은 1시간 후에 녹을 치즈가 있는 칸이므로 값을 2로 변경해주고 count의 값을 1 증가시킵니다.
      3. 만약 그렇지 않다면 재귀함수를 통해 아직 탐색하지 않은 칸들을 탐색합니다.
3. 2번의 반복문이 끝났을 때의 result 값이 판에 더이상 치즈가 없을 때의 시간이므로 해당 값을 출력하고 count 값이 1시간 전에 남아있는 치즈의 개수이므로 해당 값 역시 출력합니다.