2636 - 치즈

문제

2636번: 치즈
문제가 길어 링크로 대체했습니다.

코드

#include <bits/stdc++.h>
using namespace std;

int a[104][104];
bool visited[104][104];
vector<pair<int,int>> v;
int n,m,cnt,cnt2;
const int dy[4] = {-1,0,1,0};
const int dx[4] = {0,1,0,-1};

void go(int y, int x){
	visited[y][x] = 1;
	if(a[y][x] == 1){
		v.push_back({y,x});
		return;
	}
	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || ny >=n || nx <0 || nx >= m || visited[ny][nx])continue;
		go(ny,nx);  
	}
	return;
}

int main(){
	cin >> n >> m;
	for(int i = 0; i <n; i++){
		for(int j = 0; j <m; j++){
			cin >> a[i][j];
		}
	}
	
	while(1){
		cnt2= 0;
		fill(&visited[0][0], &visited[0][0] + 104*104, 0);
		v.clear();
		go(0,0);
		for(pair<int,int>b : v){
			cnt2++;
			a[b.first][b.second] = 0;
		}
		bool flag = 0;
		for(int i = 0; i <n; i++){
			for(int j = 0; j <m; j++){
				if(a[i][j] != 0) flag = 1;
			}
		}
		cnt++;
		if(!flag)break;
	}
	
	cout << cnt << '\n' << cnt2 << '\n';
}

풀이

설계 과정부터 소개하겠습니다.
출력 값이 모두 녹는데 걸리는 시간, 녹기 1시간 전 남아있는 치즈 조각이므로 뭔가 카운트 해야할 일이 생길듯 했다.
핵심 로직을 생각해보면 "공기와 닿아있는가" 였다.
이를 구현하기 위해서 처음에 치즈 좌표를 담아서 치즈에서 '0'이 닿으면 바깥면이라고 판단하자 라고 생각했는데 안쪽에서도 바깥이라는 오류가 발생했다.
주어진 조건이 맨 바깥은 무조건 '0'이었기 때문에 그 점을 이용해서 맨 바깥에서 젤 처음 '1'이 닿으면 바깥에 있는 치즈라 생각하고 이 좌표를 vector에 담아서 '0'으로 바꾸려고 생각했다.
모든 과정은 2중 for문으로 돌아 1이 나오지 않을때까지 while문을 돌도록 하였다.
녹기 직전 치즈의 갯수를 출력해야 하므로 '1'을 '0'으로 바꾸는 과정에서 cnt2를 해주었다.

결과

후기

핵심 로직에 대한 코드를 생각해내는게 생각보다 어려웠다.
너무 생각이 틀에 박혀 있어서 그런지 한 방향으로만 고민하게 됐다.
구현하고 보니 생각보다 어렵지 않아서 아쉬웠고 다음엔 안풀리면 새로운 방식을 고집하려고 노력해봐야겠다.