[EPPER/14회 8번]토마토 보관(중-3)

// 실제 시험에서는 solution 함수를 사용한다는 점을 감안하고 풀이해주세요.
#include <iostream>
#include <algorithm>
#include <vector>
/*

이런 문제가 나오면 태두리에 -1을 넣어서 계산에 용이하게 만든다! 


토마토가 모두 익을 수 있는 상황인가? 아닌가(-1) 를 먼저 판단해야함 


모두 익을 수 없다 -> -1 
=> 토마토는 자발적으로 익을 수 x -> 무조건 근접한 곳에 익은 토마토가 존재하는지 확인
isPossible을 이용함 


모두 익을수 있다 -> 며칠이나 걸리는지 판단하기

얼마나 걸릴지 모르기 떄문에 while문을 사용하고
while문의 내용은 
토마토 배열을 스캔하면서 
익은 토마토(1)이 있으면 상/하/좌/우 를 검사해서 이들이 0인경우 check배열에 true로 표시해둔다

스캔을 마쳤으면 check부분을 전부 오리지널 토마토 배열에서 1로 변경한다 
-> 이게 1회 즉, 1일이 경과한 것이므로 day++해준다 

while문이 끝나면 day를 리턴 





*/



using namespace std;





int tomato[1002][1002];
bool checked[1002][1002];

bool isPossible(int M, int N){

	//주의! 태두리를 채웠으므로 모든 곳은 index 0은 태두리 부분임! 
	for (int i = 1; i < M + 1; i++) {
		for (int j = 1; j < N + 1; j++) { //익게 하는게 불가능한지 확인
			if (tomato[i][j] == 0 && tomato[i - 1][j] == -1 && tomato[i + 1][j] == -1 && tomato[i][j - 1] == -1 && tomato[i][j + 1] == -1) {// 순서대로 본인(0) 상(-1) 하(-1) 좌(-1) 우(-1) 
				return false; //이런게 한개라도 존재하면 전부 익는게 불가능함 
			}
		}
	}
	
	
	return true;
}


bool isAll(int M, int N) { //전부 익었는지 확인하는 함수
	for (int i = 1; i < M + 1; i++) {
		for (int j = 1; j < N + 1; j++) {
			if (tomato[i][j] == 0)
				return false;
		}
	}
	return true;
}

int cntDate(int M, int N) {
	int daycnt = 0;
	
	//애초에 전부 익을수 있는 경우인지 확인 
	bool P = isPossible(M,N);
	
	//익을 수 있는 경우라면 
	if(P){
		while (1) {
			if (isAll(M, N)) //전부 익었으면 -> 종료 
				break;
			for (int i = 1; i < M + 1; i++) {
				for (int j = 1; j < N + 1; j++) { //익은 토마토인데 상하좌우가 안익은 토마토이면 체크해둠
					if (tomato[i][j] == 1 && tomato[i - 1][j] == 0) //상
						checked[i - 1][j] = true;
					else if (tomato[i][j] == 1 && tomato[i + 1][j] == 0) // 하 
						checked[i + 1][j] = true;
					else if (tomato[i][j] == 1 && tomato[i][j - 1] == 0) //좌
						checked[i][j - 1] = true;
					else if (tomato[i][j] == 1 && tomato[i][j + 1] == 0) //우 
						checked[i][j + 1] = true;
				}
			}
			for (int i = 1; i < M + 1; i++) { //체크했던 토마토 한번에 익게 함(1로 변경)
				for (int j = 1; j < N + 1; j++)
					if (checked[i][j])
						tomato[i][j] = 1;
			}
			daycnt++; //하루가 지남
		}
		return daycnt;
	}
	else{
		return -1;
	}
}

int main() {
	int N, M;

	scanf("%d %d", &N, &M);
	for (int i = 0; i < M + 2; i++) { //익을 수 있는지 확인하기 쉽게 하려고 상하좌우 한줄씩 추가 후 -1로 초기화
		for (int j = 0; j < N + 2; j++)
			tomato[i][j] = -1;
	}
	
	//실제 값을 입력받아 초기화 다시함 
	for (int i = 1; i < M + 1; i++) {
		for (int j = 1; j < N + 1; j++) {
			scanf("%d", &tomato[i][j]);
		}
	}

	printf("%d", cntDate(M, N));

}

 

 

Queue를 이용(BFS트리 탐색)

// 실제 시험에서는 solution 함수를 사용한다는 점을 감안하고 풀이해주세요.
#include <iostream>
#include <vector>
#include <queue>

using namespace std;


vector<vector<int>> makeFence(vector<vector<int>>v, int N, int M){
	
	
	vector<int> line(N+2,-1);
	
	
	for(int i=0;i<M;i++){
		v[i].insert(v[i].begin(),-1);
		v[i].push_back(-1);
	}
	
	v.insert(v.begin(),line);
	v.push_back(line);
	
	return v;
	
}


int solution(vector<vector<int>>tomatoV, int N, int M){
	int tomatoNum=0;
	queue<pair<int,int>> q;
	
	vector<vector<int>>tomato = makeFence(tomatoV,N,M);
	
	for(int i=0;i<M+2;i++){ //토마토 배열을 돌면서  
		for(int j=0;j<N+2;j++){
			
			if(tomato[i][j] == 1){ // 익은 토마토(1)를 발견하면 
				q.push(pair<int,int>(i,j)); // 해당 토마토 위치 i,j를 저장 
			}
			else if(tomato[i][j] == 0){ //안익은 토마토에 대해서는(0)
				tomatoNum++; // 안익은 토마토의 수를 증가시킴 
			}
		}
	}
	
	int x,y; //pop된 토마토의 배열 위치 
	
	while(!q.empty()){
		pair<int,int> p = q.front(); //맨 처음껄 꺼냄
		q.pop();//없앰 
		
		x = p.first; //꺼낸거 x좌표
		y = p.second; // 꺼낸거 y좌표
		
		//내 상하좌우에 안익은 토마토가 있는지 검사 
		//토마토를 익게만듬(tomato[i][j] + 1을 거기에 대입) -> tomatoNum 감소시키기 -> 큐에 집어넣기 
		if(tomato[x-1][y] == 0 )//상
		{
			tomato[x-1][y] = tomato[x][y] + 1;
			tomatoNum--;
			q.push(pair<int,int>(x-1,y));
		}
		if(tomato[x+1][y] == 0 )//하
		{
			tomato[x+1][y] = tomato[x][y] + 1;
			tomatoNum--;
			q.push(pair<int,int>(x+1,y));
		}
		if(tomato[x][y-1] == 0 )//좌
		{
			tomato[x][y-1] = tomato[x][y] + 1;
			tomatoNum--;
			q.push(pair<int,int>(x,y-1));
		}
		if(tomato[x][y+1] == 0 )//우
		{
			tomato[x][y+1] = tomato[x][y] + 1;
			tomatoNum--;
			q.push(pair<int,int>(x,y+1));
		}
						

		
	}
	
	if(tomatoNum==0) return tomato[x][y]-1;
	else return -1;
	
	
	
}


int main() {
	vector<vector<int>>tomato;
	vector<int> tomato_line;
	int to;
	int N,M;
	
	cin>>N>>M;
	
	for(int i=0;i<M;i++){
		for(int j=0; j<N; j++){
			cin>>to;
			tomato_line.push_back(to);
		}
		tomato.push_back(tomato_line);
		tomato_line.clear();
	}
	
	cout<<solution(tomato,N,M);
	
	
	
	return 0;
}