[G3] 백준 2638번 치즈 C++ 너비 우선 탐색, 해시맵, 구현, 시뮬레이션

리뷰

 

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

적어도 2번 이상 외부 공기에 노출되면 치즈가 녹는 문제, 유사 치즈문제보다 살짝 더 조건이 까다로웠다.

 

 

유사 문제

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

 

 

전역 변수

• n : 맵의 세로 크기를 저장할 변수
• m : 맵의 가로 크기를 저장할 변수
• dx, dy : 4방향 탐색을 위한 방향 배열
• lst : 맵 정보를 저장하기 위한 정수형 2차 배열
• v : 방문 정보를 저장하기 위한 정수형 2차 배열
• dic : 각 치즈가 공기에 노출된 횟수를 저장할 해시맵
• Pos : 시뮬레이션 시 사용하기 위한 x, y좌표를 담는 구조체
• air : 탐색을 진행해야 할 공기를 저장하기 위한 Pos타입의 큐

 

함수

1. input

void input()

 

맵의 크기와 맵 정보를 입력 받고 저장하기 위한 함수

1. n, m값을 입력받은 뒤 n * m크기의 맵 정보를 입력 받아준다.
2. 이 때 값이 1인 경우 x좌표 + y좌표 * 100를 키로 갖고, 값은 0으로 dic에 초기화 해준다.

 

2. solution

int solution()

 

치즈가 모두 녹을 때 까지 시뮬레이션을 돌리는 함수

1. 정수형 변수 ans를 0으로 초기화 해준다.
2. air에 초기 위치인 0, 0을 push해준다.
3. 초기 위치 0, 0을 v배열에 방문처리 해준다.
4. ans를 전위 증가 시키며 무한 루프를 실행해 준다.
5. floodfill함수를 통해 공기를 확산 시키는 로직을 수행해 준다.
6. spread함수를 통해 맵에 남아있는 치즈가 있는지 체크하고, 치즈가 없다면 루프를 종료한다.
7. 루프가 종료된 후 ans에 저장된 값을 리턴해 준다.

 

3. floodfill

void floodfill()

 

공기의 확산을 시뮬레이션 하기 위한 함수

1. air가 빌 때 까지 while루프를 수행해 준다.
2. 각 시뮬레이션 단계에서 요소 한개씩을 뽑아 해당 공기의 좌표를 cx, cy로 초기화 해준다.
3. 4방향 탐색을 진행하며 맵의 범위 안에 있고, 방문 처리가 되지 않은 경우 이동을 진행해 준다.
4. 이동한 위치가 맵 상에서 0, 즉 공기라면 방문처리 후 해당 공기를 air에 push 해준다.
5. 이동한 위치가 맵 상에서 1, 즉 치즈라면 해당 위치의 x좌표 + y좌표 * 100을 키로 하는 dic의 value를 증가시킨다.

 

4. spread

bool spread()

 

현재 치즈가 닿은 외부 공기의 개수를 체크하고 조건에 맞으면 치즈를 녹이는 함수

1. 제거해야할 key값을 저장할 정수형 벡터 del를 초기화 해준다.
2. dic의 요소를 순회하며 키를 100으로 나눈 나머지를 cx, 100으로 나눈 몫을 cy로 초기화 한다.
3. 만약 현재 요소의 값이 2이상이라면 맵에서 해당 위치의 값을 0으로 바꾸어 준다.
4. 또한 해당 위치를 방문처리 후 air에 해당 좌표값을 push해준다.
5. 해당 요소를 dic에서 지우기 위해 del에 해당 key값을 추가해 준다.
6. 모든 dic요소를 순회한 경우 del에 저장된 key값, 즉 녹은 치즈들을 dic에서 지워준다.
7. 위 작업을 마치고 만약 dic이 비었다면 true를, 아니라면 false를 리턴해 준다.

 

문제풀이

1. input함수를 통해 맵의 크기와 맵 정보를 입력 받아준다.
2. solution함수를 통해 시뮬레이션을 진행하고 리턴 받은 값을 출력해 준다.

 

트러블 슈팅

1. 매 시간마다 남아 있는 치즈에서 4방향 탐색을 진행했더니 바로 시간 초과가 났다.
2. 따라서 매번 치즈의 상태를 체크하는것이 아닌 누적된 상태를 체크하는 방법이 뭐가 있을지 고민했다.
3. 배열을 쓰기엔 매번 100 * 100크기의 맵을 순회하는 것이 너무 비효율적으로 다가왔다.
4. 따라서 x, y좌표를 적절히 매핑하여 key로 사용하는 해시맵을 사용하는 아이디어를 떠올렸다.
5. spread함수에서 무한 루프가 발생했었는데 for문 내에서 직접 erase를 해준게 원인이었다, for문이 종료된 후에 dic에서 녹은 치즈를 삭제해 주니 해결되었다.

 

참고 사항

• x, y모두 0 ~ 99까지의 인덱스를 가지므로 x는 그대로, y를 * 100을 한 값을 key로 사용하면 무결성을 보장한다.
• floodfill함수에서 치즈를 만났을 경우에는 방문 처리를 해주면 안된다.

 

정답 코드

#include<iostream>
#include<queue>
#include<algorithm>
#include<unordered_map>
#include<vector>
using namespace std;

int n, m;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int lst[100][100];
int v[100][100];
unordered_map<int, int> dic;
struct Pos {
	int x, y;
};
queue<Pos> air;

bool spread() {
	vector<int> del;
	for (auto i : dic) {
		int cx = i.first % 100, cy = i.first / 100;
		if (i.second >= 2) {
			lst[cx][cy] = 0;
			v[cx][cy] = 1;
			air.push({ cx, cy });
			del.push_back(i.first);
		}
	}
	for (int i : del) dic.erase(i);
	if (dic.empty()) return true;
	return false;
}

void floodfill() {
	while (!air.empty()) {
		Pos pos = air.front(); air.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]) {
				if (!lst[nx][ny]) {
					v[nx][ny] = 1;
					air.push({ nx, ny });
				}
				else dic[nx + ny * 100]++;
			}
		}
	}
}

int solution() {
	int ans = 0;
	air.push({ 0, 0 });
	v[0][0] = 1;
	while (++ans) {
		floodfill();
		if (spread()) break;
	}
	return ans;
}

void input() {
	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]) dic[i + j * 100] = 0;
		}
	}
}

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

	input();
	cout << solution();
}