[C++]백준2638번 치즈

오늘은 백준2638번 치즈 문제를 풀어보도록 하자.

이번엔 다른 치즈문제이다. 적어도 2변 이상 공기와 접촉해야 치즈가 녹는다. 이전 문제는 한 변만 닿아도 녹았었다.

따라서 이번엔 map을 3차원으로 받았다. 왜냐하면 몇 번 공기와 접촉했는지 cnt해주기 위함이다.

문제는 다음과 같다.

                               [접근법]

  1. 가장자리엔 치즈가 놓일 수 없으므로 0,0부터 쭉 돌려준다. 

  2. 중요한건 만일 map[my][mx][0] == 1 일 때 인데 이 부분에서 조건을 줄 때 방문을 했던 안했던 탐색을 해야한다는 것이다.
  
  3. 만일 map[my][mx][0]이 1이면 map[my][mx][1]을 1씩 증가시켜주고 bfs가 끝나면 map[my][mx][1]이 2 이상이었을 때 map[my][mx][0]은 0처리를 해준다.

                                     [코드]
                                     -BFS-
#include <iostream>
#include <queue>
using namespace std;
int map[100][100][2];
bool visit[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int R, C, answer = 0, cnt = 0;
struct pos {
	int y;
	int x;
};
queue<pos>Q;

void Init_visit() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visit[i][j] = false;
		}
	}
}

void check_cnt() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j][1] >= 2) {
				map[i][j][0] = 0;
				cnt--;
			}
			map[i][j][1] = 0;
		}
	}
}

bool Inbound(int y, int x) {
	return y >= 0 && x >= 0 && y < R && x < C;
}

void bfs() {
	while (!Q.empty()) {
		int y = Q.front().y;
		int x = Q.front().x;

		Q.pop();

		for (int i = 0; i < 4; i++) {
			int my = y + dir[i][0];
			int mx = x + dir[i][1];

			if (Inbound(my, mx)) {
				if (!visit[my][mx] && map[my][mx][0] == 0) {
					Q.push({ my,mx });
				}
				if (map[my][mx][0] == 1) {
					map[my][mx][1]++;
				}
				visit[my][mx] = true;
			}
		}
	}
	answer++;
}

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

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j][0];
			if (map[i][j][0] == 1) {
				cnt++;
			}
		}
	}
	while (cnt != 0) {
		Q.push({ 0,0 });
		visit[0][0] = true;
		bfs();
		Init_visit();
		check_cnt();
	}
	cout << answer;
}

                                     -DFS-
#include <iostream>
using namespace std;
int map[100][100][2];
bool visit[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
int R, C, answer = 0, cnt = 0;

void Init_visit() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			visit[i][j] = false;
		}
	}
}

void check_cnt() {
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (map[i][j][1] >= 2) {
				map[i][j][0] = 0;
				cnt--;
			}
			map[i][j][1] = 0;
		}
	}
}

bool Inbound(int y, int x) {
	return y >= 0 && x >= 0 && y < R && x < C;
}

void dfs(int y, int x) {
	visit[y][x] = true;
	for (int i = 0; i < 4; i++) {
		int my = y + dir[i][0];
		int mx = x + dir[i][1];

		if (Inbound(my, mx)) {
			if (!visit[my][mx] && map[my][mx][0] == 0) {
				dfs(my, mx);
			}
			if (map[my][mx][0] == 1) {
				map[my][mx][1]++;
			}
		}
	}
}

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

	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j][0];
			if (map[i][j][0] == 1) {
				cnt++;
			}
		}
	}
	while (cnt != 0) {
		dfs(0, 0);
		check_cnt();
		Init_visit();
		answer++;
	}
	cout << answer;
}