[백준] 2636-치즈(C++)

문제링크:www.acmicpc.net/problem/2636

2636번: 치즈

 

bfs를 사용한 구현문제였습니다.

단계를 나누어 구현하시면 편합니다.

 

• 0. 치즈가 다 녹았는지 확인
• 1. bfs를 통해서 외부 공기 표시하기
• 2. 외부 공기에 닿는 치즈를 찾아서 없애기
• 3. 최근 치즈의 개수 저장하기(0이 아닐때만)

 

중간중간에 테스트 코드를 통해서 올바르게 진행 되는지 확인하면 더 어려운 문제가 나오더라도 당황하지 않고 푸실 수 있을겁니다!

 

혹시 bfs 구현이 어렵다면 쉬운 bfs 문제들 풀어보시면 그냥 bfs 코드자체에 익숙해지셔야 합니다.

아래는 정답코드입니다.

#include <iostream>
#include <queue>
using namespace std;

int result = 0;
int result2 = 0;
int n, m;
bool arr[101][101] = { 0, };

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

int solved(){

	//0. init
	bool jud = false;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (arr[i][j] == 1)
				jud = true;

	if (jud == false)
		return 1;

	//1. bfs 
	bool visited[101][101] = { 0, };
	queue <pair <int, int>> que;
	que.push(make_pair(1, 1));
	visited[1][1] = 1;

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];

			if (ny >= 1 && ny <= n && nx >= 1 && nx <= m) 
				if (arr[ny][nx] == 0 && visited[ny][nx] == 0) {
					que.push(make_pair(ny, nx));
					visited[ny][nx] = 1;
				}
			
		}

	}
	//2. 닿는 곳 찾아 없애기
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (arr[i][j] == 1) {

				for (int u = 0; u < 4; u++) {
					int ad_y = i + y_ar[u];
					int ad_x = j + x_ar[u];

					if (visited[ad_y][ad_x] == 1) {
						arr[i][j] = 0;
						break;
					}
				}
			}

	//3. 최근 갯수
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (arr[i][j] == 1)
				cnt++;
	if(cnt!=0)
		result2 = cnt;
	result++;


	/*
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << arr[i][j] << ' ';
		cout << endl;
	}*/

	return 0;

}


int main() {
	ios_base::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];
			if (arr[i][j] == 1)
				result2++;
		}

	while (1) {
		if (solved() == 1)
			break;
	}


	cout << result << endl;
	cout << result2 << endl;
	return 0;
}