백준 7576번 : 토마토 _ C++

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

7576번: 토마토

 

#그래프 #BFS 알고리즘 #gold5

 

회고

 

✔ 문제 접근

처음 문제 접근했을 때 시작점을 어떻게 잡아야 할지 갈피를 잡지 못했다.

알고보니 시작점은 익은 토마토 좌표를 입력받을 때 큐에 넣어주고 해당 좌표로 설정해주면 되는거였다.

 

✔ 배열 관리

처음엔 visit 배열은 방문했는지 여부만 저장하였고 익는데 걸리는 시간은 따로 dist 배열을 통해 저장해주었는데 다시 풀어보면서 굳이 그럴 필요성을 느끼지 못해 dist 배열은 없애고 visit 배열을 통해 걸리는 시간을 업데이트 해줬다.

 

✔  답 경우의 수

 

• 토마토가 처음부터 다 익어있는 경우
• 토마토가 다 익지 못하는 경우
• 토마토가 전부 다 익는데 걸리는 시간

각각 checkAll, check, findMax 함수를 통해 구현해줬다.

해당 함수들을 굳이 모듈화 하지 않고 한번에 체크 할 수 있을거 같은데 그 부분은 좀 더 고민해봐야겠다.

 

✔ 고난

처음 문제를 다 풀고 예제를 입력했을 때 답이 엉뚱하게 나와서 한참을 고민했는데 알고보니 가로,세로 입력을 잘못한것이었다.. 그걸 찾지 못해 괜히 코드 다 갈아엎고 다시 작성해봤었다 ㅜ

그래도 덕분에 dist 배열을 없애고 visit 배열에 날짜 업데이트 하는 방향으로 갈 수 있었다.

 

+) 가로, 세로를 잘못 입력한 문제점을 발견하기 전에 첫번째 예제를 넣었을 때 자꾸 답이 9가 나오길래 왜 그런가 했더니 알고보니 원래 익어있던 토마토는 익는 일자 카운트를 하지 않는다는 것을 알아차리지 못했었다. 그래서 이미 익어있는 좌표들은 0으로 세팅해주고 다른 좌표들은 입력할때 -1으로 세팅해줬다.

 

코드

 

#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;

int m, n;
queue<pair<int, int>> q;
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
int box[MAX][MAX];
int visit[MAX][MAX];

void bfs() {
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int tX = x + dx[i];
			int tY = y + dy[i];

			if ((0 <= tX && tX < n) && (0 <= tY && tY < m) &&
				visit[tX][tY] == -1 && box[tX][tY] != -1) {
				visit[tX][tY] = visit[x][y] + 1;
				q.push({ tX,tY });
			}
		}
	}
}
bool checkAll() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (box[i][j] == 0) return false;
		}
	}
	return true;
}
bool check() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == -1 && box[i][j] == 0)
				return false;
		}
	}
	return true;
}

int findMax() {
	int max = -1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] > max)
				max = visit[i][j];
		}
	}
	return max;
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> box[i][j];
			visit[i][j] = -1;
			if (box[i][j] == 1) {
				visit[i][j]++;
				q.push({ i,j });
			}
		}
	}
	if (checkAll()) {
		cout << 0;
		return 0;
	}
	bfs();
	if (!check()) {
		cout << -1;
		return 0;
	}
	else {
		cout << findMax();
	}
	return 0;
}