BOJ 7576 : 토마토 ☆

[문제]

- M*N크기 배열에 토마토 정보가 주어진다. (1=익음, 0=안 익음, -1=없음)

- 익은 토마토에 인접한 곳에 있는 토마토는 다음날 익는다. 

- 며칠이 지나야 모든 토마토가 익을 것인가

- 입력 : M,N, M*N배열 정보

- 출력 : 날짜

 

[풀이]

- bfs로 배열을 탐색한다. (기본 껍데기 활용)

- q.front()로 현재 노드를 설정하고 상하좌우 노드를 탐색한다.

   => 이 때, 날짜를 계산하기 위해 map[next]의 값을 map[cur]+1로 해준다.

- 마지막에 map의 최댓값-1을 하면 모든 토마토가 익는 날짜를 알 수 있다.

- bfs가 끝나고 map에 0이 남아있으면 다 익지 않은 것이므로 -1로 예외처리 필요.

 

- 틀린 원인 : 배열을 입력 받을 때 m,n 헷갈려서..

[코드]

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

#define X first
#define Y second

const int MAX = 1001;
int M, N;
int map[MAX][MAX];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { -1,1,0,0 };
queue<pair<int, int>> q;

void bfs() {
	while (!q.empty()) {
		pair<int, int>cur = q.front();
		q.pop();

		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir];
			int ny = cur.Y + dy[dir];
			if (nx < 0 || nx >= N || ny < 0 || ny >= M)continue;
			if (map[nx][ny] != 0)continue;

			//cur을 기준으로 상하좌우를 탐색함
			//0인 노드를 발견하면 cur에 위치한 값에 +1을 해준다
			map[nx][ny] = map[cur.X][cur.Y] + 1;
			q.push({ nx,ny });
		}
	}
}

int main() {
	memset(map, 0, sizeof(map));
	
	cin >> M >> N;
	//주의 N->M 순서로 봐야한다
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int temp;
			cin >> temp;
			map[i][j] = temp;
			// 익은 토마토의 위치를 q에 push
			if (temp == 1) {
				q.push({ i,j });
			}
		}
	}

	bfs();

	int max = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				cout << "-1" << "\n"; return 0;
			}
			//map에 존재한 최대값이 토마토가 다 익은 날짜가 될 것임
			if (max < map[i][j]) max = map[i][j];
		}
		
	}
	cout << max - 1 << "\n";

	return 0;
}