[알고리즘/문제풀이] [BOJ 1012번] 유기농 배추

유기농 배추 문제는 이전에 풀었던 단지 번호 붙이기 문제와 매우 유사한 문제입니다. 따라서 코드를 재활용하여 문제를 해결할 수 있습니다. 

이 문제에서는 Flood fill 기법을 활용하여 그룹의 개수만 세어줌으로써 문제를 해결할 수 있습니다. 따라서 그룹 내 원소의 개수를 더 이상 셀 필요가 없습니다.

단지번호 붙이기 문제와 유사하므로 자세한 설명은 단지 번호붙이기 문제를 참고하기 바랍니다.

2021.09.09 - [알고리즘/문제풀이] - [알고리즘/문제풀이][BOJ 2667번] 단지번호붙이기

[알고리즘/문제풀이][BOJ 2667번] 단지번호붙이기

#include<stdio.h>
#pragma warning(disable : 4996)
//https://ark-hive.tistory.com/

int T;
int M, N, K;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
int X, Y;

int map[100][100];
int wp, rp;

int cnt = 1;

struct Queue {
	int x;
	int y;
};

struct Queue queue[2000200];
struct Queue temp;

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

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

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

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j] = 0;
		}
	}
	cnt = 1;
}

int main(void) {
	scanf("%d", &T);
	for (int l = 0; l < T; l++) {
		scanf("%d %d %d", &M, &N, &K);

		init();

		for (int i = 0; i < K; i++) {
			scanf("%d %d", &X, &Y);
			map[Y][X] = 1;
		}

		
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 1) {
					wp = 0;
					rp = 0;
					cnt++;
					enqueue(j, i);
					map[i][j] = cnt;

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

							enqueue(nx, ny);
							map[ny][nx] = cnt;
						}
					}
				}
			}
		}

		printf("%d\n", cnt - 1);
	}
}

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

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