2636. 치즈

 

Solution 

 

1. 데이터를 받아 map에 저장합니다
2. (0.0)으로 dfs함수를 호출합니다. 문제에서 무조건 0,0은 치즈가 없다고 하였기에 이점을 이용하여 공기에 접촉된 치즈를 찾습니다.
3. 찾은 치즈는 list 큐에 저장합니다. 
4. 여기서 포인트는 각 치즈의 시간을 알아야 된다는 것입니다. 저는 이를 해결하기위해 자료구조 큐와 (1110,1110)이라는 값을 넣어줬습니다. => 큐를 이용하면 순차적으로 pop이 되어 순서를 지킬 수 있습니다. 한번 dfs함수를 돌면서 들어온 값들은 동일한 시간을 가지고 있기에 이후 값과 섞이지 않고 관리할 수 있습니다. 하지만, 이렇게 한다고 해도 시간이 변경되는 기준점을 찾을 수 없습니다. 그래서 저는 임의값 (1110,1110)을 넣어 시간이 변경되는 시점을 체크하였습니다. 1110값은 그냥 input으로 절대 들어올 수 없는 값을 설정하였습니다. 
5. 그래서 큐도 빌 때까지 돌면서 dfs함수를 이용하여 치즈를 녹이고 주위에 있는 치즈 상태를 변경해주고 만약 구멍이있다면 이것까지 처리해주었습니다. 참고로 공기와 접촉된 치즈는 2, 공기가 유입된 공간은 -1, 그냥 치즈는 1입니다. 
6. 그래서 마지막으로 시간이 변경되는 타이밍이고 리스트가 비었다면, while문을 멈추고 출력해줍니다. 

 

 

Key Point

최근에 논리오류보다는 pop()의 위치를 잘못 정하거나 하는 등의 실수가 많이 생깁니다. 이러한 실수는 오류를 잡기도 힘들고 일부케이스에만 오류가 나기에 반례를 찾아 하나하나 확인해야됩니다. 

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include<algorithm>
using namespace std;
typedef struct A {
	int i;
	int j;
};
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
int map_size = 0;
int map[120][120] = { 0 };


int n, m;
queue <A> list;
void dfs(int i, int j) {
	map[i][j] = -1;
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] <n && j + dy[k] >= 0 && j + dy[k] < m) {
			if (map[i + dx[k]][j + dy[k]] == 1) {
				map[i + dx[k]][j + dy[k]] = 2;
				list.push({ i + dx[k],j + dy[k] });
			}
			if (map[i + dx[k]][j + dy[k]] == 0) {
				dfs(i + dx[k], j + dy[k]);
			}	
		}
	}
}


int main(void) {

	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0, 0);
	int time = 0;
	int before = list.size();
	list.push({ 1110,1110 });
	while (!list.empty()) {
		int i = list.front().i;
		int j = list.front().j;
		list.pop();
		if (i == 1110 && j == 1110) {
			time++;
			if (list.empty())
				break;
			before = list.size();
			list.push({ 1110,1110 });

			i = list.front().i;
			j = list.front().j;
		}

		dfs(i, j);
	
	}
	cout << time << endl;
	cout << before << endl;

	return 0;
}