[백준 BOJ] 7576_토마토

 

https://www.acmicpc.net/problem/7576

7576번: 토마토

 

BFS 문제를 풀어보았다. BFS는 큐를 사용해서 탐색을 구현하는 것으로 알고 있었는데 어떤식으로 큐에 넣어야 할 지 감이 잘 안잡혔다. 코드플러스 강의에서 다운받은 백준님의 자료와 블로그를 참조하여 코드를 짰다. 

 

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

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int tomato[1000][1000];
queue<pair<int, int>>q;

int main() {
	int M, N; 
	int total = 0; // 토마토가 있는 칸과 토마토가 없는 칸의 합을 확인해주기 위함
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) { 
				q.push({i, j}); 
			}
			else if (tomato[i][j] == -1) { // 토마토가 없음
				total++;
			}
		}
	}
	int size = 0;
	int day = 0;

	while (!q.empty()) {
		size = q.size(); // 익은 토마토의 개수
		total += size; // 토마토가 없는 칸 + 익은 토마토가 있는 칸

		if (total == N * M) { //토마토가 없는 칸 + 익은 토마토가 있는 칸의 값이 전체 창고의 크기와 같으면 끝
			cout << day;
			break;
		}
		for (int i = 0; i < size; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (0 <= nx && nx < N && 0 <= ny && ny < M) {
					if (tomato[nx][ny] == 0) { // 주변이 익지 않은 토마토라면
						tomato[nx][ny] = 1;
						q.push({ nx, ny });
					}
				}
			}
		}
		day++;
	}
	if (total != N * M) {
		cout << -1;
	}
	return 0;
}

 

• 구현 방법

	int M, N; 
	int total = 0; // 토마토가 있는 칸과 토마토가 없는 칸의 합을 확인해주기 위함
	cin >> M >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] == 1) { 
				q.push({i, j}); 
			}
			else if (tomato[i][j] == -1) { // 토마토가 없음
				total++;
			}
		}
	}

    - 입력은 토마토의 상태를 나타내주기 때문에 이차원 배열로 입력을 받았다.

    - 값이 1이면 익은 토마토이므로 큐에 해당 토마토의 위치를 넣었다. 

    - 토마토가 없는 칸의 개수를 total 변수에 넣는다.

 

	int size = 0;
	int day = 0;

	while (!q.empty()) {
		size = q.size(); // 익은 토마토의 개수
		total += size; // 토마토가 없는 칸 + 익은 토마토가 있는 칸

		if (total == N * M) { //토마토가 없는 칸 + 익은 토마토가 있는 칸의 값이 전체 창고의 크기와 같으면 끝
			cout << day;
			break;
		}
		for (int i = 0; i < size; i++) {
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int j = 0; j < 4; j++) {
				int nx = x + dx[j];
				int ny = y + dy[j];
				if (0 <= nx && nx < N && 0 <= ny && ny < M) {
					if (tomato[nx][ny] == 0) { // 주변이 익지 않은 토마토라면
						tomato[nx][ny] = 1;
						q.push({ nx, ny });
					}
				}
			}
		}
		day++;
	}

    - BFS 탐색 시작

 

    - 익은 토마토가 있는 큐의 사이즈를 반환하고 토마토가 없는 칸의 개수인 total과 합친다. total의 현재 값은 '토마토가 없는 칸' + '익은 토마토'가 있는 칸이다.

 

    - total의 값을 전체 칸의 개수인 N*M의 값과 비교한다. total 값과 N*M의 값이 같으면 탐색이 끝난것이다. 토마토가 없는 칸은 무슨짓을 해도 토마토가 들어갈 수 없고, 큐에 들어가는 것은 익은 토마토의 개수들이기 때문이다.   

 

    - for 문은 size만큼 반복, 즉 현재 익은 토마토에 대해 주변으로 퍼져나갈 수 있는지 확인하는 것이다.

 

    - 주변탐색(4방향)을 진행하고 주변이 0이면 1로 바꿔 준 뒤, 큐에 push 한다.

 

    - while loop의 마지막에서 day를 늘려주며 반복한다.

 

 

 

• 어려웠던 부분
  1. 큐에 어떤것을 넣어야 할지
  2. 토마토를 다 익히지 못하는 상황의 경우 어떻게 종료 시켜야 하는지
  3. 날짜를 어떻게 세야하는 지
• 놓쳤던 부분
  1. total 변수를 따로 두고 토마토가 없는 칸의 개수와 토마토가 있는 칸의 개수를 합해주는 것
  2. 종료조건 
• 배운 점 : 뭔가 풀고나니 엄청 어려운 문제는 아니었는데 구현 방법을 잘 생각하지 못한것 같다. 그래도 4방향으로 확산하는 문제유형은 비슷한데, 그 부분은 이제 접근을 할 수 있게 된 것 같다