[백준] 2638번 치즈 - C/C++/JAVA

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

2638번: 치즈

문제

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 1>

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

<그림 2>

<그림 3>

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표시된다. 또한, 각 0과 1은 하나의 공백으로 분리되어 있다.

출력

출력으로는 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 정수로 첫 줄에 출력한다.

---

문제 풀이 순서는 다음과 같다.

1. 치즈 내부와 외부를 구분

2. 치즈 외부와 닿는 면적 구하기

3. 녹이기

 

    치즈 내부와 외부를 구분하려면 치즈가 아닌 한 점에서 1 을 만나면 멈추는 dfs를 진행하여 그 부분이 외부라는 것을 저장해두면 된다. 이때 1을 만나면 flag를 설정하여 만약 flag 가 설정되지 않았다면 치즈가 더 이상 남아있지 않은 것이므로 반복문을 중단하고 정답을 출력한다.

    치즈 외부와 닿는 면적을 구할 때 유의해야할 점은 기존의 배열을 바로 변경할 경우 변경된 지점이 다른 지점에 영향을 줄 수 있으므로 배열의 복사본을 두어 복사본에 외부와 닿는 면적을 저장해둔 후 한 번에 치즈를 녹이도록 한다.

 

[C/C++ 풀이]

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int arr[110][110] = {0};
int temp[110][110] = {0};
int temp2[110][110] = { 0 };
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int n, m,tick=0;
bool flag;

void fill_air(int x, int y) {
	if (arr[x][y]) { flag = true; return; }
	
	temp[x][y] = 2;
	for (int i = 0; i < 4; i++) {
		if (x + dx[i] >= 0 && x + dx[i] <= n + 1 && y + dy[i] >= 0 && y + dy[i] <= n + 1 && !temp[x+dx[i]][y+dy[i]])
			fill_air(x + dx[i], y + dy[i]);
	}
}

void melt() {
	memset(temp2, 0, sizeof(temp2));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			for (int k = 0; k < 4; k++) {
				if (temp[i+dx[k]][j+dy[k]] == 2) {
					temp2[i][j]++;
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (temp2[i][j] >= 2)
				arr[i][j] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}

	while (1) {
		memset(temp,0, sizeof(temp));
		flag = false;
		fill_air(0,0);
		if (!flag) break;
		tick++;
		melt();
	}
	cout << tick;
	return 0;
}

[Java 풀이]

import java.util.*;

public class Main {
	static int[][] arr; 
	static int[][] temp ;
	static int[][] temp2;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n,m,tick;
	static boolean flag;
	
	public static void main(String[] args){     
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		arr = new int[110][110];
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		while(true) {
			temp = new int[110][110];
			flag = false;
			fill_air(0,0);
			if(flag == false) break;
			tick++;
			temp2 = new int[110][110];
			melt();
		}
		System.out.println(tick);
	}
	
	static void fill_air(int x,int y) {
		if(arr[x][y] == 1) {flag = true ; return;}
		
		temp[x][y] = 2;
		
		for(int i=0;i<4;i++) {
			if (x + dx[i] >= 0 && x + dx[i] <= n + 1 && y + dy[i] >= 0 && y + dy[i] <= n + 1 && temp[x+dx[i]][y+dy[i]] == 0)
				fill_air(x + dx[i], y + dy[i]);
		}
		
	}
	
	static void melt() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				for (int k = 0; k < 4; k++) {
					if (temp[i+dx[k]][j+dy[k]] == 2) {
						temp2[i][j]++;
					}
				}
			}
		}

		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (temp2[i][j] >= 2)
					arr[i][j] = 0;
			}
		}
	}
}

---

 

    문제를 보고 며칠전에 푼 빙산 문제와 유사하다는 것을 느꼈다. 다른 점은 치즈 내부의 존재였는데 이를 어떻게 해결할지 고민하다가 이 역시 dfs로 순회하여 외부만 인지하면 되겠다고 생각했다. 나머지 부분은 저번 문제와 동일하게 진행하였다. 다 풀고 나니 저번 빙산 문제와 너무 비슷한 거 같아 좀 머쓱했다!

    자바 공부를 코딩테스트 문제를 풀 수 있을 정도로는 이론을 배운 것 같아 사용하였다. 문자열도 아니고 그냥 배열이라 메서드 같은 경우 C++ 함수 코드를 그대로 가져다 써도 될 정도였다. 다만 public class를 Main으로 해야 채점 시 컴파일 에러가 안 난다! 그리고 Scanner 클래스는 한 번만 생성해주면 그다음부터 해당 Stream으로부터의 입력은 매개변수를 통해 입력받을 수 있다. 코딩 테스트 문제여서 그런지 이게 java와 c++ 이 크게 다른 점은 모르겠다. 다른 사람들의 코드를 보아도 비슷하게 짠것 같은데 알고리즘이 동일한데 객체지향 프로그래밍이라고 크게 무언가 다를까 싶다!