백준 - 1012 유기농 배추

백준 사이트의 1012번 dfs문제 유기농 배추의 풀이법을 정리해보겠습니다. dfs가 아닌 bfs로도 풀이가 가능한 문제이지만 저는 dfs로 풀었습니다.

 

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

1012번: 유기농 배추

문제는 링크로 첨부하겠습니다.

이문제는 직관적으로 dfs를 수행하면 바로 해결이 가능한 문제입니다. 배추가 심어진 위치를 배열에 저장해놓고 배추가 심어진 위치를 만날때마다 dfs를 호출합니다. 그리고 방문한 위치는 표시해놓고 dfs함수 내부에서 현재 위치의 위아래좌우에 배추가 심어져있고 방분한적이 없을 경우 dfs함수를 재귀호출하여 이어진 배추의 개수를 구하면 됩니다.

 

다음은 제가 풀이한 소스코드입니다.

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <queue>

using namespace std;
int map[50][50];
int visit[50][50];
int block[50];
int block_num;
int T, M, N, K;

int index[4][2] = { {1,0}, {0,1}, {-1,0}, {0,-1} };//아래 오른쪽 위 왼쪽 순서대로

void dfs(int x, int y) {
	visit[x][y] = 1;
	//printf("%d %d\n", x, y);
	for (int i = 0; i < 4; i++) {
		int xIdx = x + index[i][0];
		int yIdx = y + index[i][1];
		if (xIdx < 0 || xIdx >= N || yIdx < 0 || yIdx >= M)
			continue;

		if (map[xIdx][yIdx] == 1 && visit[xIdx][yIdx] == 0) {
			dfs(xIdx, yIdx);
		}
	}
}

void sort() {

}

void debug() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			printf("%d", map[i][j]);
		}
		printf("\n");
	}
}
void clear() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			map[i][j] = 0;
			visit[i][j] = 0;
			block_num = 0;
		}
	}
}

int main()
{
	block_num = 0;
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d %d %d", &M, &N, &K);
		for (int j = 0; j < K; j++) {
			int horizon, vertical;
			scanf("%d %d", &horizon, &vertical);
			map[vertical][horizon] = 1;
		}
		/*printf("\n");
		debug();*/
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 1 && visit[i][j] == 0) {
					dfs(i, j);
					block_num++;
				}
			}
		}
		block[i] = block_num;
		clear();
	}
	for(int i = 0; i < T; i++)
		printf("%d\n", block[i]);
}