[G4] 백준 2636번 치즈 C++ 너비 우선 탐색, 플러드 필, BFS, Flood Fill

리뷰

 

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

매 시간이 지날 때 마다 공기 근처에 있는 치즈가 녹는 전형적인 플러드 필 문제

 

 

전역 변수

• n : 맵의 세로 길이를 저장할 변수
• m : 맵의 가로 길이를 저장할 변수
• remain : 남아 있는 치즈 조각의 개수를 저장할 변수
• last : 치즈가 완전히 녹기 전 남아있던 치즈 조각의 개수를 저장할 변수
• ans : 치즈가 완전히 녹기 까지 걸린 시간을 저장할 변수
• lst : n * m크기의 맵 정보를 저장할 정수형 2차 배열
• v : 방문 처리를 체크하기 위한 정수형 2차 배열
• dx, dy : 4방향 탐색을 하기 위한 방향 배열
• Pos : 시뮬레이션에 사용하기 위한 좌표를 정의할 구조체
• h : 구멍 정보를 저장하기 위한 Pos타입의 큐
• c : 이번에 녹을 치즈 정보를 저장하기 위한 Pos타입의 큐

 

함수

1. melt

void melt()

 

이번 시간에 녹을 수 있는 치즈를 녹이기 위한 함수

1. Pos타입 큐 c가 빌 때까지 루프를 수행하며 큐 안의 요소를 한개씩 꺼내준다.
2. 맵 상에서 해당 좌표의 값을 0으로 변경해 준다.
3. Pos타입 큐 h에 해당 좌표를 추가해 준다.
4. remain를 감소시켜 남은 치즈 조각의 개수를 줄여준다.

 

2. bfs

void bfs()

 

너비 우선 탐색을 통해 구멍의 4방향을 탐색하여 플러드 필을 수행하기 위한 함수

1. Pos타입 큐 h가 빌 때까지 루프를 수행하며 큐 안의 요소를 한개씩 꺼내준다.
2. 해당 좌표로부터 4방향 탐색을 진행한다. 범위 내에 있으면서 방문하지 않은 지점을 만났을 경우 로직을 수행해 준다.
3. 우선 방문처리를 진행하고 맵 상에서 값이 0이라면 c에 1이라면 h에 좌표를 push해준다.
4. 모든 탐색이 종료된 후에 melt함수를 호출하여 공기 주변의 치즈를 녹여준다.

 

문제풀이

1. n, m값을 입력 받고, n * m크기의 맵 정보를 입력 받아준다, 이때 값이 1인경우 remain을 증가시켜 준다.
2. h에 초기값인 0, 0을 넣어준다, 외곽의 경우 무조건 빈 상태이므로 외곽의 아무 좌표나 넣어줘도 상관 없다.
3. remain이 1이상일 경우 while루프를 수행해 준다.
4. 매 턴마다 ans를 증가시켜 주고 last에 remain값을 저장해 준 뒤 bfs함수를 호출한다.
5. remain이 0이되어 루프가 종료되었을 경우 ans와 last를 줄 바꿈을 기준으로 출력해 준다.

 

참고 사항

모든 좌표를 확인할 필요 없이 방금 녹인 치즈 좌표로 부터 탐색을 이어나가주면 된다.

 

 

정답 코드

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

int n, m, remain, last, ans;
int lst[100][100];
int v[100][100];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

struct Pos {
	int x, y;
};
queue<Pos> h;
queue<Pos> c;

void melt() {
	while (!c.empty()) {
		Pos pos = c.front(); c.pop();
		int cx = pos.x, cy = pos.y;
		lst[cx][cy] = 0;
		h.push({ cx, cy });
		remain--;
	}
}

void bfs() {
	while (!h.empty()) {
		Pos pos = h.front(); h.pop();
		int cx = pos.x, cy = pos.y;

		for (int i = 0; i < 4; ++i) {
			int nx = cx + dx[i], ny = cy + dy[i];
			if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny]) {
				v[nx][ny] = 1;
				if (!lst[nx][ny]) h.push({ nx, ny });
				else c.push({ nx, ny });
			}
		}
	}
	melt();
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> lst[i][j];
			if (lst[i][j]) remain++;
		}
	}

	h.push({ 0, 0 });
	while (remain) {
		ans++;
		last = remain;
		bfs();
	}
	cout << ans << "\n" << last;
}