백준 2636(치즈)

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

2636번: 치즈

문제에서 요구하는 게 무엇인지 제대로 파악하고, 논리를 구성해야 하는 문제. 

 

치즈가 공기와 닿으면, 녹는다. 

다 녹을 때 까지 얼마나 걸리는가, 녹기 직전 치즈의 양은? 

 

 

가장 핵심은 먼저 초기에 공기와 닿는 치즈의 좌표를 구하는 일이었다. 

 

가장자리의 공기부터 시작해서 이어진 모든 공기를 구분하고, 가장 처음 만난 치즈는 무조건 치즈의 가장자리가 되므로 그 좌표들을 치즈의 테두리로 정한다. 

 

치즈의 테두리를 queue1에 저장한 뒤 테두리의 치즈가 녹았을 때, 공기와 접촉하는 치즈의 테두리가 무엇인지 구한다. 

 

위 방법을 반복한다. 

 

테두리의 치즈를 구하는 방법은 dfs와 bfs 모두 사용할 수 있겠지만 dfs의 구현이 더 쉽다고 생각해서 dfs로 구현하였다. 

 

	if (cheeze[i][j]) {
		if (!visited[i][j]) {
			visited[i][j] = true;
			q.push(make_pair(i, j));
		}
		return;
	}
	visited[i][j] = true;

	for (int s = 0; s < 4; s++) {
		int x = i + dx[s];
		int y = j + dy[s];
		if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
		if (!visited[x][y]) init(x, y);
	}

 

 

 

치즈를 만나면 안 쪽의 치즈까지 이어지지 않도록 바로 return 을 해준다. 

 

그리고, 처음 만난 치즈는 테두리의 치즈이므로 queue에 넣어준다.

 

 

테두리 치즈가 녹은 뒤에 속의 테두리 치즈를 구하는 방법에서 주의해야 할 점이 있다. 

 

안 쪽에 공기가 있을 때 처리가 까다로운데 공기를 만나면 그 공기와 인접한 공기들을 모두 visited 로 만들고 앞서 init 함수처럼 dfs방식으로 공기와 처음 만나는 테두리의 치즈를 구해준다. 

 

위 방법을 위해서 따로 add1, add2함수를 만들어서 사용하였다. 

 

void add2(int i, int j) {
	if (cheeze[i][j]) {
		if (!visited[i][j]) {
			visited[i][j] = true;
			q.push(make_pair(i, j));
		}
		return;
	}
	visited[i][j] = true;

	for (int s = 0; s < 4; s++) {
		int x = i + dx[s];
		int y = j + dy[s];
		if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
		if (!visited[x][y]) add2(x, y);
	}
}

 

 

위 add함수 처리를 완료하고 나면 논리적으로 더 간단해진다. 

 

테두리의 치즈가 녹은 뒤 

 

테두리의 치즈 좌표를 이용해서 bfs 탐색을 해준다. 안 쪽 테두리 치즈를 구하는 것이다. 

치즈가 다 녹을 때까지 반복. 이 때 횟수를 count 해줄 cnt 변수와 치즈의 양을 저장하는 num 변수를 이용해서 문제의 답을 구한다. 

 

queue를 두 개 쓰는 단순한 bfs 턴제 문제이다. 이전 문제에서 언급하였다. 

 

#include<iostream>
#include<queue>
#include<utility>
using namespace std;
#define MAX 101


queue<pair<int, int> > q;
queue<pair<int, int> > q2;
int N, M, a, cnt=0, num;
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0,0,1,-1 };
bool cheeze[MAX][MAX] = { false };
bool visited[MAX][MAX] = { false };



void init(int i, int j) {
	if (cheeze[i][j]) {
		if (!visited[i][j]) {
			visited[i][j] = true;
			q.push(make_pair(i, j));
		}
		return;
	}
	visited[i][j] = true;

	for (int s = 0; s < 4; s++) {
		int x = i + dx[s];
		int y = j + dy[s];
		if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
		if (!visited[x][y]) init(x, y);
	}
}

void add1(int i, int j) {
	if (cheeze[i][j]) {
		if (!visited[i][j]) {
			visited[i][j] = true;
			q2.push(make_pair(i, j));
		}
		return;
	}
	visited[i][j] = true;

	for (int s = 0; s < 4; s++) {
		int x = i + dx[s];
		int y = j + dy[s];
		if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
		if (!visited[x][y]) add1(x, y);
	}
}

void add2(int i, int j) {
	if (cheeze[i][j]) {
		if (!visited[i][j]) {
			visited[i][j] = true;
			q.push(make_pair(i, j));
		}
		return;
	}
	visited[i][j] = true;

	for (int s = 0; s < 4; s++) {
		int x = i + dx[s];
		int y = j + dy[s];
		if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
		if (!visited[x][y]) add2(x, y);
	}
}

void solve() {
	while (!q.empty() || !q2.empty()) {
		num = 0;
		while (!q.empty()) {
			num++;
			int i = q.front().first;
			int j = q.front().second;
			q.pop();
			for (int s = 0; s < 4; s++) {
				int x = i + dx[s];
				int y = j + dy[s];
				if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
				if (!visited[x][y]) {
					if (cheeze[x][y]) {
						visited[x][y] = true;
						q2.push(make_pair(x, y));
					}
					else add1(x, y);
				}
			}
			if (q.empty()) cnt++;
		}
		if (!q2.empty()) num = 0;
		while (!q2.empty()) {
			num++;
			int i = q2.front().first;
			int j = q2.front().second;
			q2.pop();
			for (int s = 0; s < 4; s++) {
				int x = i + dx[s];
				int y = j + dy[s];
				if (x < 0 || y < 0 || x > N - 1 || y > M - 1) continue;
				if (!visited[x][y]) {
					if (cheeze[x][y]) {
						visited[x][y] = true;
						q.push(make_pair(x, y));
					}
					else add2(x, y);
				}
			}
			if (q2.empty()) cnt++;
		}
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> a;
			if (a == 1) cheeze[i][j] = true;
		}
	}
	init(0, 0);
	solve();
	cout << cnt << "\n" << num << "\n";
}