[백준] 7576번: 토마토 [C++]

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색

문제 링크: https://www.acmicpc.net/problem/7576

7576번: 토마토

 

 

 

 

【 풀이 】

 

이 문제는 시작점이 여러 개로 주어질 수 있기 때문에, 여러 정점에서 동시에 출발할 수 있도록 해주어야 한다.

즉 모든 시작점(1) 들을 큐에 밀어 넣어서, bfs를 정점들마다 번갈아가면서 탐색할 수 있게끔 해주면 된다.

 

그리고 날짜를 기록하는 게 곧 탐색의 거리를 의미하기도 하기에

배열마다 거리를 계산해서 그 최댓값을 출력해 보았다.

 

배열 값이 모두 0인 경우 (이걸 모르고 있었어서 헤맸다)

배열 값이 모두 차있는 경우 (0이 없는 경우)

정도만 주의하면 될 것 같다.

 

 

【 코드 】

 

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

int front_y[4] = { -1,1,0,0 };
int front_x[4] = { 0,0,-1,1 };

queue<pair<int, int>>pos;
int tomato[1001][1001];
int dist[1001][1001];
int visited[1001][1001];
int m, n;

// 시작해야하는 정점(vertex)들을 큐에 넣어주는 함수
// bfs 를 각 정점들마다 번갈아가면서 하게 만들어 줌.
void vertex(int y, int x) {
	pos.push(make_pair(y, x));
}

void bfs(int here_y, int here_x) {
	visited[here_y][here_x] = true;
	pos.push(make_pair(here_y, here_x));
	dist[here_y][here_x] = 0;

	while (pos.empty() == false) {
		if (!visited[here_y][here_x])
			visited[here_y][here_x] = true;
		here_y = pos.front().first;
		here_x = pos.front().second;
		pos.pop();

		for (int dir = 0; dir < 4; dir++) {
			int next_y = here_y + front_y[dir];
			int next_x = here_x + front_x[dir];

			if (next_y < 0 || next_x < 0)	continue;
			if (next_y >= n || next_x >= m)	continue;
			if (tomato[next_y][next_x] == -1)continue;			
			if (tomato[next_y][next_x] == 1)continue;
			if (visited[next_y][next_x])	continue;

			visited[next_y][next_x] = true;
			pos.push(make_pair(next_y, next_x));
			dist[next_y][next_x] = dist[here_y][here_x] + 1;
			tomato[next_y][next_x] = 1;
		}
	}
}

int main() {
	bool isPossible = false;
	bool isZero = true;
	int i, j;
	cin >> m >> n;

	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			cin >> tomato[i][j];
			if (tomato[i][j] != 0)	isZero = false;
			if (tomato[i][j] == -1) visited[i][j] = -1;
			if (tomato[i][j] == 1)	vertex(i, j);
		}
	
	if(!isZero)
		bfs(pos.front().first, pos.front().second);

	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++)
			if (visited[i][j] == 0) { isPossible = true; break; }
		if (isPossible) { cout << -1; break; }
	}

	if (!isPossible) {
		int max = 0;
		for (i = 0; i < n; i++) 
			for (j = 0; j < m; j++) 
				if (max < dist[i][j])
				max = dist[i][j];
		cout << max;
	}

	return 0;
}