[C++] 7576번 : 토마토

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

7576번: 토마토

풀이

상하좌우만 탐색이 가능하다고 주어졌습니다. 추가로 idea 자체가 2178번과 매우 유사함이 느껴집니다.

토마토가 익어가는 상황과 distance를 구해야 하는 상황이 결국 BFS를 요함을 캐치해야합니다.

다만 2178번 문제와는 달리 출발점 1에서 동시에 탐색을 수행해야할 것만 같습니다.

코드로 동시에 구현할 수는 없음을 우리는 잘 알고 있습니다.. 출발점이라는 것을 유심히 생각해보면

각 출발점을 우리는 Queue를 통해 예약할 수 있고 동시는 아니지만 서로 독립적으로 돌 수 있게 할 수 있습니다.

어차피 distance 배열의 값은 따로 초기화해줄테니깐요.

여기까지가 핵심 idea이고, 이후는 다시 배열을 돌아줘야겠다 생각하면 되고 남은 건 구현입니다!

문제에서 요구하는 것은 출발점에서 distance를 0으로 설정하고 더해나가라인데

저는 BFS 과정에서 distance가 0인 요소는 아직 방문하지 않았다는 것으로 나타내기 위해 시작점들의 distance를 모두 1로 설정하였습니다.

 

내 코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int board[1000][1000];
int dis[1000][1000];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int main() {
	int M, N, day = 0;
	cin >> M >> N;
	queue<pair<int, int>> q;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> board[i][j];
			if (board[i][j] == 1) {
				q.push({ i,j });
				dis[i][j] = 1;
			}
		}
	}
	while (!q.empty()) {
		pair<int, int> cur = q.front(); q.pop();
		for (int dir = 0; dir < 4; dir++) {
			int x = cur.X + dx[dir];
			int y = cur.Y + dy[dir];
			if (x < 0 || y < 0 || x >= N || y >= M) continue;
			if (dis[x][y] || board[x][y] == -1) continue;
			q.push({ x,y });
			board[x][y] = 1;
			dis[x][y] = dis[cur.X][cur.Y] + 1;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == 0) {
				cout << -1;
				return 0;
			}
			day = max(day, dis[i][j]);
		}
	}
	cout << day - 1;
}

 

감격스럽게도 모든 idea를 떠올렸네요. 감사합니다. 감사합니다.