[C++]백준2636번 치즈

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

map이 100 x 100이고 조건도 까다롭지 않아서 BFS, DFS 모두 사용가능한 문제였다. 그래서 둘 다 사용하여 구현해보았다.

문제는 다음과 같다.

                               [접근법]
                               
                               -BFS-
1. 치즈는 공기와 맞닿아 있는 곳이 녹아 없어진다. 따라서 BFS를 이용할 때는 공기(0)를 타고 큐에 넣어 관리를 하다가 치즈(1)를 만나면 0으로 바꿔주고 
cheese_cnt를 감소, 그 자리를 방문처리, answer를 증가시켜준다.

2. while문에서 만일 cheese_cnt == 0이라면 종료 후, 턴과 다 녹기 전 치즈의 갯수를 출력한다.

                               -DFS-
                               
1. 마찬가지로 공기(0)를 만나면 방문처리를 해주고 DFS함수를 다시 타고 들어간다. 그러다 치즈(1)를 만나면 0으로 바꿔주고, cheese_cnt를 감소, 그자리를 방문처리, answer를 증가시킨다.

2. 여기서 중요한건 DFS함수가 끝나고 방문해제를 해주면 안된다는 것이다. 왜냐면 1->0으로 된 곳을 방문처리 해제를 하면 무한루프에 빠지게 된다.

                                     [코드]
                                     
                                     -BFS-
#include <iostream>
#include <queue>
using namespace std;

int R, C, cheese_cnt = 0, answer, turn = 0;
int map[100][100];
bool visit[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };
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;
		}
	}
}

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

void bfs() {
	answer = 0;
	Q.push({ 0,0 });
	visit[0][0] = true;

	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]) {
					if (map[my][mx] == 0) {
						Q.push({ my,mx });
						visit[my][mx] = true;
					}
					else if (map[my][mx] == 1) {
						answer++;
						cheese_cnt--;
						visit[my][mx] = true;
						map[my][mx] = 0;
					}
				}
			}
		}
	}
}

int main() {
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				cheese_cnt++;
			}
		}
	}
	while (cheese_cnt != 0) {
		turn++;
		bfs();
		Init_visit();
	}
	cout << turn << '\n' << answer << '\n';
}

                                     -DFS-
#include <iostream>
using namespace std;

int R, C, cheese_cnt = 0, answer, turn = 0;
int map[100][100];
bool visit[100][100];
int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

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

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

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

		if (Inbound(my, mx) && !visit[my][mx]) {
			if (map[my][mx] == 0) {
				visit[my][mx] = true;
				dfs(my, mx);
			}
			else {
				visit[my][mx] = true;
				answer++;
				cheese_cnt--;
				map[my][mx] = 0;
			}

		}
	}
}

int main() {
	cin >> R >> C;

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) {
				cheese_cnt++;
			}
		}
	}
	while (cheese_cnt != 0) {
		turn++;
		answer = 0;
		visit[0][0] = true;
		dfs(0, 0);
		Init_visit();
	}
	cout << turn << '\n' << answer << '\n';
}