백준] 7576 : 토마토

7576번: 토마토

입력	출력
6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1	8
6 4 0 -1 0 0 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1	-1
6 4 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1	6
5 5 -1 1 0 0 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 -1 -1 -1 0 0 0 0 0 0	14
2 2 1 -1 -1 1	0

 

 

✍문제 풀이

 ✔ 토마토가 익는 과정은 아래와 같다.

 

 ✔ 처음 시작이 '1'일 때, 닿아 있는 면'0'이면 '1'로 변합니다. 따라서 BFS로 풀어줍니다.

 

 ✔ 방법

     ①  초기에 주어지는 map을 입력받을 때, queue에  '1'인 칸 좌표를 저장한다.

        > 이유는 1인 칸이 여러 개일 때, 동시에 일수를 계산하기 위해서이다.

     ②  bfs( )를 실행한다.

          ② -1. queue가 empty( )가 아닐 때까지 반복한다.

          ② -2. x, y 좌표 값을 저장하고, 방문 체크를 해준다.  x, y 좌표 값을 변수에 저장했다면 queue는 지워준다.'-1'이면 무시한다. '0'이면 '1'로 바꾼 후에 일수를 더해준다.

          ② -3. 상하좌우 이동이 가능한지 체크하기 위해 반복한다.

                  ② -3-(1).  토마토 상자 범위를 벗어나면 무시한다. 또한 상자 안의 원소가 '-1'(토마토가 없으면)이면 무시한다.

                  ② -3-(2).  방문하지 않은 곳이고, 상자에 토마토가 있으면('0')이면

                                    queue에 좌표를 저장하고, 방문체크를 하고, 일수를 더해준다.

     ③  bfs 탐색 후, '0'인 칸이 하나 이상이면 -1을 return한다.

                                  '0'인 칸이 없으면 일수를 return한다.

 

 

🌱 정답코드

+) 처음에 짜고 틀린 코드

 

     ①  '1'인 칸을 찾는다

     ②  '-1'이면 무시한다. '0'이면 '1'로 바꾼 후에 일수를 더해준다.

     ③  bfs 탐색 후, '0'인 칸이 하나 이상이면 -1을 return한다.

     ④  '0'이 없다면 일수 -1인 값을 출력한다.

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

int N, M;
int map[1001][1001];
bool check[1001][1001];

// 상하좌우 이동
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int day; // 토마토가 익은 일수 체크

void bfs(int x, int y){
	queue<pair<int, int>> q;
	
	q.push({x, y});
	check[x][y] = true; // 방문 체크
	
	while(!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		
		// 상하좌우 토마토 익는 것 체크
		for(int i = 0; i < 4; i++){
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			// map 범위 벗어나면 무시
			if(nx < 0 || ny < 0 || nx > N || ny > M) continue;
            // ********
            // 범위는 if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
			
			// 토마토가 없으면 무시
			if(map[nx][ny] == -1) continue;
			
			// 익지 않은 토마토가 있으면 익혀주기
			if(map[nx][ny] == 0){
				map[nx][ny] = map[x][y] + 1;
				q.push({nx, ny});
				check[nx][ny] = true;
			}
		}
	}
}

int main() {
	int answer = 0;
	
	cin >> M >> N;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> map[i][j];
		}
	}
	
	int oneCheck = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(map[i][j] == 1){
				bfs(i, j);
				oneCheck++;
			}
		}
	}

	int max = 0, zeroCheck = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(map[i][j] == 0) zeroCheck++;
			
			if(max < map[i][j]) max = map[i][j];
		}
	}
	
	if(zeroCheck >= 1) answer = -1;
	else if(oneCheck > 1 && zeroCheck == 0){
		answer = (max / oneCheck) + 1;
	}
	else answer = max - 1;
	
	cout << answer;
	
	return 0;
}

6 4 1 -1 0 0 0 0 0 -1 0 0 0 0 0 0 0 0 -1 0 0 0 0 0 -1 1	else if(oneCheck > 1 && zeroCheck == 0){    answer = (max / oneCheck) + 1; } 위 코드로 어떻게든 정답 코드로 만들었는데,
'1'이 여러 개고, '0'을 '1'로 만들 때는 일수를 체크하지 못함..	결과는 5여야 하지만 가 출력됨..ㅎ

 

틀린 코드인줄 알면서 한 번 제출해봄 ㅎ..ㅎ

 

 

---

 ✔ 1인 칸이 여러 개일 때, 동시에 확인하려면 queue에 1이 든 공간의 좌표 값을 저장하고,

 bfs를 돌릴 때, 각 좌표를 하나씩 꺼내서 확인해주면 된다.

 

내가 처음 짰던 코드는 1이 여러 개일 때는 생각하지 못하고 짠 코드이다.

 

 

 

 

 

 

---

풀이 참고

1. kswims.tistory.com/24	하루가 지날 때마다 익은 토마토들은 큐에 넣어주고 다음날이 되면 해당 큐에 토마토를 빼면서 그 토마토로 익을 수 있는 토마토를 넣어주면 된다. 큐에 들어간다는 건 토마토가 익었다는 뜻이므로 계속해서 큐에 들어가는 size를 축적시킨 다음 그 값이 M*N와 같아질 때가 모든 토마토가 다 익는 날이다. 큐에는 아무런 토마토가 안남아있는데 안익은 토마토가 남아있을 경우엔 -1을 출력해준다
2. https://jaimemin.tistory.com/605	1. 창고를 입력 받는데 1이면 덱에 넣고, -1이면 noTomato를 증가시킵니다. 2. 창고에 있는 토마토가 모두 익었다면 0을 출력하고 아니라면 BFS 함수를 호출합니다. 3. BFS 함수를 호출하였는데 덱이 비어있다면 모든 토마토가 익을 수 없는 경우이므로 -1을 반환합니다. 4. 현재 덱 사이즈만큼 for문을 돌리면서 front에 있는 좌표를 꺼내 창고 범위 내에 있는 상하좌우에 있는 안 익은 토마토를 익힌 뒤 해당 좌표를 덱에 넣고 front를 pop 시킵니다. 5. 현재 덱 사이즈만큼 for문을 돌린 뒤에는 하루가 지나므로 day를 증가시킵니다. 6. 덱이 비었고 allRipe 함수가 true를 반환하면 day를 반환하고, 덱이 비었는데 allRipe 함수가 false를 반환하면 모든 토마토가 익을 수 없으므로 -1을 반환합니다.
3. zoonvivor.tistory.com/131	1. 토마토가 익은 점들을 큐에 넣어준다. (동시 다발적으로 일어나기 때문에 큐를 사용한 BFS) 2. 익은 토마토 상하좌우를 탐색하며 익지 않은 토마토가 있으면 그 위치를 큐에 넣어준다. (그 위치의 값은 최대 일수를 계산하기 위해 전 위치 +1 을 해준다.) 3. 큐가 빌때까지 계속해준다. 4. 전체 토마토들을 탐색하여  익지않은 토마토(0 값) 하나라도 있으면 -1를 출력한다.  5. 그 외는 최대 일수를 출력한다.
4. jdselectron.tistory.com/55	토마토 창고 크기 m x n을 입력 m x n 크기의 창고에서 각각의 상태(1,0,-1)를 배열에 저장한다. 그리고 토마토가 익은상태(1)는 queue에 바로 넣는다. BFS 알고리즘을 통해 탐색을 진행하는데, 익은 토마토(1)의 상하좌우의 4방향을 탐색하게 되고, 각각의 상태가 토마토 창고의 크기를 안벗어나면서 안익은 상태(0)라는 조건에 해당된다면 탐색한 칸 = 이미 익은토마토(1) + 1을 하게 된다. 즉, 이미 익은 토마토는 1이고 날짜가 하루 지나면 1+1, 그 다음날은 2 + 1이 되는 형태이다. BFS 탐색이 끝나고 최종적인 상태에서, 만약 토마토 창고 내부에 아직도 익지않은 토마토(0)이 존재한다면 토마토가 들어있지 않은 칸(-1)으로 인해 토마토가 전부 익지 못하는 상황이므로 -1을 출력한다. 반대로 모든 토마토는 다 익었을때, 배열의 값에 따라 날짜가 결정이 되는데, 배열안에 가장 큰 값이 1이라면 앞서 말한 조건(안익은 상태라면)을 만족못해서 한번도 +1이 되지않아 기본 값(익어있는 상태)인 1에서 고정된다. 즉, 전체가 초기부터 익어있다고 볼 수 있다. 그래서 0을 출력한다. 마지막으로 배열안에 가장 큰 값이 1보다 크다면 해당 배열 값 - 1이 전체가 다 익는데 걸린 날이라고 볼 수 있다. 여기서 -1은 기본 값이 1부터 시작하므로 마지막에는 1을 빼줘야한다.

음.. 사실 다른 분의 문제 풀이 설명을 다 이해하지 못했다...

그러나 4번 블로그 분의 풀이가 많은 도움이 되었다.

 

입력받을 때, '1'이 곳의 좌표값을 queue에 넣는다.

이후, bfs( ) 함수를 실행할 때, 1이었던 공간을 번갈아가며 순차적으로 실행하니까 정확한 답이 나온다.