[백준 2636] 치즈

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

2636번: 치즈

#include <cstdio>
#include <queue>
int N, M;	// 행 열
int board[100 + 2][100 + 2];
int visited[100 + 2][100 + 2];
int cheese;

struct _qt
{
	int x, y;
};

std::queue<_qt> Q;

void input()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &board[i][j]);
			if (i == 0 || i == N - 1) Q.push({ i, j });
			if (j == 0 || j == M - 1) Q.push({ i, j });
		}
	}
}

void BFS()
{
	static int dir_x[4] = { 0, 0 ,1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	std::queue<_qt> Tmp;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] == 0) {
				Q.push({ nx, ny });
				visited[nx][ny] = 1;
			}
			else if (board[nx][ny] == 1) {
				Tmp.push({ nx , ny });
				visited[nx][ny] = 1;
			}

		}
	}
	Q = Tmp;
}



int simul()
{
	int days = 0;
	while (1) {
		cheese = Q.size();
		BFS();
		if (Q.empty()) return days;
		days++;
	}
}




int main()
{
	input();
	int ans = simul();
	printf("%d\n%d\n", ans, cheese);
	return 0;
}

 

 

(22. 09. 18 풀이)

이 로직을 이해하는데 한달 넘게 걸린 나... ^^.. 작고 소중한 내 뇌.... ^^..

#include <cstdio>
#include <queue>
int N, M;
int cheese_map[100 + 2][100 + 2];
int visited[100 + 2][100 + 2];

struct _st
{
	int x;
	int y;
};


std::queue<_st> Q;

void input(void)
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &cheese_map[i][j]);
			if (i == 0 || i == N - 1 || j == 0 || j == M - 1) Q.push({ i, j });
		}
	}
}


int BFS(void)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	std::queue<_st> C = {};

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > M - 1) continue;
			if (visited[nx][ny]) continue;
			if (cheese_map[nx][ny] == 1) {	// 가장자리 
				C.push({ nx, ny });
				cheese_map[nx][ny] = 0;
			}
			else Q.push({ nx, ny });
			visited[nx][ny] = 1;
		}
	}
	Q = C;	// 가장자리 부분만 담김 
	return Q.size();
}


void get_cheese(void)
{
	std::queue<int> ans;
	while (1) {
		int tmp = BFS();
		if (tmp == 0) break;
		ans.push(tmp);
	}
	printf("%d\n%d", ans.size(), ans.back());
}

int main()
{
	input();
	get_cheese();
	return 0;
}

 

내가 맨날 바보라고는 하는데 사실은 전혀 바보가 아닌 애가 알려준 풀이를 공유해보고자 한다. 나만볼수도.. ㅋㅋ

 

처음 이 문제를 해결할 때는 공기부분을 3으로, 구멍 부분을 0으로 표시하고 루프를 엄청 돌렸다. 그런데 그 방법 보다는 상기 풀이가 훨씬 깔끔한 것 같다. 기억해서 다음에도 써먹어야지... 

 

 

// input( ) 함수 

해당 문제에서는 풀이의 가장 결정적인 설명이 있다. 바로 "가장자리는 반드시 공기"라는 조건이다. 그래서 데이터를 입력받아주면서 가장자리(무조건 공기일) 좌표를 큐에 받아주었다. 

 

 

// get_cheese( ) 함수

치즈가 모두 녹기 한 시간 전에 남아있는 조각의 개수를 얻기 위해 큐를 선언하였다. 

무한루프를돌면서 BFS( ) 함수가 리턴하는 남아있는 치즈의 개수를 tmp 변수에 받는데, 만약 tmp가 0이면 더이상 치즈가 없는 것이므로 루프를 빠져나온다. 그리고 루프를 빠져나오기 전 마지막으로 큐에 삽입한 정수가 "치즈가 모두 녹기 한 시간 전 남아있는 조각의 개수"가 되고, 이때의 큐 사이즈가 "공기 중에서 치즈가 모두 녹아 없어지는데 걸린 시간" 이다. 

 

 

// BFS( ) 함수

해당 함수 안에서 선언한 C 라는 이름의 큐는 매 시간마다의 가장자리 좌표를 담기 위한 큐이다. 

input 함수에서 받은 "반드시 공기인 부분"의 좌표가 들어있는 Q가 빌 때 까지 루프를 돌리면서, 만약 가장자리를 만나면 그 좌표를 C에 담고, cheese_map에서 해당 좌표를 0으로 바꾸고 방문처리 해준다(다음 호출때는 이 좌표의 칸들이 모두 공기가 됨). 만약 공기(0)를 만나면 Q에 해당 좌표를 담아주고 방문처리 해준다. 

이렇게 한번 while 루프를 돌면 치즈의 첫번째 가장자리가 0으로 바뀌고 C에는 가장자리 좌표(두번째 BFS를 돌릴때는 반드시 공기인 부분)가 담기게 된다. 이후 Q = C; 를 통해 C 컨테이너에 들어있는 모든 좌표 정보를 Q 컨테이너에 옮겨주고 C는 날려준다. 

이때 BFS 함수의 리턴값은 치즈의 가장자리 개수 이다.