BFS & DFS - 백준 1012번 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

귀찮아서 VISITED를 잘 안쓰려고 노력하는 편이다. 

 

IDEA

상하좌우가 인접하면 이어져있다고 할 때, 이어져있는 구간? 영역?이 몇 개 인지 물어보는 문제다. 

testcase 로 여러개 구해야되는 상황이라 n,m,map등을 dfs함수로 전달해줘야해서 귀찮았다.

dfs 나 bfs 나 상관 없다. 2중 for문을 통해 map[i][j] 가 1인 곳에 대해서 dfs를 실행한다. 

dfs는 범위 내에 있으면서 새로운 좌표 (상하좌우)의 map이 1이라면 map을 0으로 만든 후 재귀문을 통해 dfs를 또 반복한다. 그러면 연결되어있는 부분들은 다 0으로 바뀌면서 서로 단절된 영역이 몇 개인 지 구할 수 있게 된다. 

 

코드  

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

int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

bool check(int x, int y , int n, int m) {
	if (-1 < x && x < n && -1 < y && y < m) return true;
	return false;
}

void dfs(int x, int y , int n, int m , int map[][50]) {
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (check(nx, ny, n, m) && map[nx][ny]) {
			map[nx][ny] = 0;
			dfs(nx, ny, n, m , map);
		}
	}
}

int main() {
	int tc;
	scanf("%d", &tc);
	for (int i = 0; i < tc; i++) {
		int n, m, s ,count = 0;
		scanf("%d %d %d", &n, &m, &s);
		int map[50][50] = { 0 };
		for (int i = 0; i < s; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			map[x][y] = 1;
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j]) {
					count++;
					map[i][j] = 0;
					dfs(i, j, n, m, map);
				}
			}
		}
		printf("%d\n", count);
	}
}