[알고리즘/문제풀이][BOJ 7576번] 토마토

토마토 문제는 BFS를 이용하는 문제입니다. BFS의 flood fill 기법을 사용하는 문제로 여러 개의 루트 노드에서 BFS를 수행한다는 점에서 다른 BFS 문제와의 차이를 확인할 수 있습니다. 문제를 해결하기 위해 BFS를 수행하기 직전 처음에 큐에 여러 개의 루트 노드를 삽입한다는 점을 제외하면 이외의 BFS flood fill 기법 응용 문제의 해결 방식과 매우 유사합니다.

BFS 문제에 대한 전형적인 구현 방식은 다음의 글에서 확인할 수 있습니다.

2021.09.07 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

[알고리즘/문제풀이][BOJ 1260번] DFS와 BFS

문제를 해결하기 위해 작성한 코드를 다음과 같습니다.

#include<stdio.h>
#pragma warning(disable : 4996)

int dx[] = {0,0,-1,1};
int dy[] = { 1,-1,0,0};
int N, M;
int map[1200][1200];
int wp, rp;

int cnt = 0;


struct Queue {
	int x, y, time;
};

struct Queue queue[1000200];
struct Queue temp;

void enqueue(int x, int y, int time) {
	queue[wp].x = x;
	queue[wp].y = y;
	queue[wp].time = time;
	wp++;
}

struct Queue dequeue() {
	return queue[rp++];
}

int empty() {
	return wp == rp;
}

int main(void) {
	scanf("%d %d", &M, &N);
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 1) {
				enqueue(j, i, 0);
			}
			else if (map[i][j] == 0) {
				cnt++;
			}
		}
	}

	if (cnt == 0) {
		printf("0\n");
		return 0;
	}

	while (!empty()) {
		temp = dequeue();
		for (int i = 0; i < 4; i++) {
			int nx = temp.x + dx[i];
			int ny = temp.y + dy[i];
			if ((nx < 0) || (nx >= M)) continue;
			if ((ny < 0) || (ny >= N)) continue;
			if (map[ny][nx] != 0) continue;
			enqueue(nx, ny, temp.time + 1);
			map[ny][nx] = 1;
		}
	}

	cnt = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 0) {
				printf("%d\n", -1);
				return 0;
			}
		}
	}

	printf("%d\n", temp.time);
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

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