개요

백준 7576번: 토마토

• 입력
  첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

  토마토가 하나 이상 있는 경우만 입력으로 주어진다.

• 출력
  여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

접근 방식

1. 익은 토마토를 큐에 미리 다 넣고 bfs를 진행하는 방식이다.

2. 일단, 조건이 몇 개 있는 데

   1. 토마토가 모두 익고 시작한다면 0을 출력
   2. 익은 토마토가 아무것도 없다면 -1출력
   3. 토마토가 안 익었고 절대 못 익는 위치에 있다면 -1 출력
      -> 구현한 코드
      (bfs가 끝난 지점에서 방문 안 했고, 안익은 토마토가 있다면 -1출력)

   	//방문을 못한 곳이 있고,"해당 지역이 익지 않은 토마토라면" -1출력
   		for (int i = 0; i < height; i++) {
   			for (int j = 0; j < width; j++) {
   				if (visited[i][j] == false && tomatoFarm[i][j]==0) {
   					cout << -1;
   					return;
   				}
   			}
   		}

코드

#include<iostream>
#include<queue>

using namespace std;
int height=0, width = 0;
//전역변수라 0초기화
int tomatoFarm[1001][1001];
//false로 초기화
bool visited[1001][1001];
queue<pair<int, int>> q;
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };

void solution();

void input() {
	//토마토가 모두 익었는지 조사하는 변수
	bool isAllRotten = true;
	cin >> width >> height;
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			cin >> tomatoFarm[i][j];
			//농장에 익은 토마토라면
			if (tomatoFarm[i][j] == 1) {
				//푸시
				q.push({ i,j });
				visited[i][j] = true;
			}
			//토마토가 하나라도 안 익은 게 있다면
			else if (tomatoFarm[i][j] == 0) {
				isAllRotten = false;

			}
		}
	}
	//토마토가 시작부터 다 익었다면
	if (isAllRotten) {
		cout << 0;
		return;
	}
	else {
		//익은 토마토가 0개라면 불가능하므로
		if (q.empty()) {
			cout << -1;
			return;
		}
		//bfs진행
		solution();
	}
	
}
void solution() {
	//시작은 0일차지만 이미 푸시되어있는 상태로 진행 되므로 level++가 실행된다 마지막에 1빼야됨
	int level=0;
	while (!q.empty()) {
		//큐 사이즈는 가변적이므로 변수 할당
		int qSize = q.size();
		for (int i = 0; i < qSize; i++) {
			pair<int, int> p = q.front();
			q.pop();
			//상하좌우 칸 조사하기 용이하게 반복문 사용
			for (int j = 0; j < 4; j++) {
				int nextH = p.first + dx[j];
				int nextW = p.second + dy[j];
				//범위 넘어가면 바로 continue
				if (nextH < 0 || nextW < 0 || nextH >= height || nextW >= width) continue;
				//이미 방문한 곳이면 continue;
				if (visited[nextH][nextW]) continue;
				//방문했다고 처리
				visited[nextH][nextW] = true;
				//다음칸이 비어있는칸이면 continue
				if (tomatoFarm[nextH][nextW] == -1) continue;
				//비어있지않다면 해당 칸 큐에 푸시해주기
				else {
					q.push({ nextH,nextW });
				}
			}
		}
		//한 큐의 사이즈만큼 끝날때마다 레벨이 증가
		level++;
	}
	//방문을 못한 곳이 있고,"해당 지역이 익지 않은 토마토라면" -1출력
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {
			if (visited[i][j] == false && tomatoFarm[i][j]==0) {
				cout << -1;
				return;
			}
		}
	}
	//반복문끝났다면 더이상 큐에 아무것도 없는 상황이므로 진행 끝
	cout << level-1;
}

int main() {
	input();

}

문풀 후생

• cout<<level-1 을 한 이유

  level을 시작할 때 0으로 설정 후, bfs를 돌렸지만
  level이 계속 1씩 증가되어서 답으로 나왔다.

  따라서 예제 1번을 예로 그리면서 생각을 해봤다.
  

  일단 bfs의 경로는 저런식으로 (4,6)좌표에서 시작해서
  적힌 숫자대로 흘러간다.

  구현한 함수의 흐름대로 적어보면

  시작 line 54 -> level 0
  -> 큐사이즈 1,
  큐에 두개 넣고 level 1
  -> 큐사이즈 2
  큐에 3개 넣고 level 2
  -> 큐사이즈 3
  큐에 4개 넣고 level 3
  -> 큐사이즈 4
  큐에 4개 넣고 level 4
  -> 큐사이즈 4
  큐에 4개 넣고 level 5
  -> 큐사이즈 4
  큐에 3개 넣고 level 6
  -> 큐사이즈 3
  큐에 2개 넣고 level 7
  -> 큐사이즈 2
  큐에 1개 넣고 level 8
  -> 큐사이즈 1
  해당 큐 pop되고 끝 level ++이여서
  level 9
  따라서 level-1 해줘야함

  이 과정에서 볼 수 있듯이 이미 시작단계에서 level이 1만큼 증가하고
  시작해서 1만큼 마지막에 빼줘야한다.

• 다른 풀이들 구경하다 본 건데,
  while(!q.empty){
  ~
  level++
  }
  이 부분을 for(;!q.empty();level++) 이렇게 for문을 이용해 활용할 수도 있었다.