1012 - 유기농 배추

문제

코드

#include <bits/stdc++.h>
using namespace std;

int t, n, m, b,ny,nx,y,x;
int a[54][54];
int visited[54][54];
const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x){
	visited[y][x] = 1;
	
	for(int i = 0; i < 4; i++){
		ny = y + dy[i];
		nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny >= n || nx >= m)continue;
		if(visited[ny][nx] == 1) continue;
		if(a[ny][nx] == 0) continue;
		dfs(ny, nx);	
	}
	return;
}

int main(){
	int ret;
	cin >> t;
	
	while(t--){
		cin >> m;
		cin >> n;
		cin >> b;
		fill(&a[0][0], &a[0][0] + 54*54, 0);
		fill(&visited[0][0], &visited[0][0] + 54*54, 0);
		ret = 0;
		
		for(int i = 0; i < b; i++){
			cin >> x >> y;
			a[y][x] = 1;
		}
		
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			if(a[i][j] == 1 && !visited[i][j]){
				dfs(i,j);
				ret++;
			}
		}
	}
	
	cout << ret << '\n';
	}
	return 0;
}

풀이

유기농 배추가 모여있는 지역 --> 즉, connected component를 구하면 되는 문제다.
연결되어 있는 모든 곳을 탐색하면서 연결된 가장 깊은 곳까지 가는 DFS 알고리즘을 사용하면 된다.
코드를 풀이해보자면 dfs 함수는 visited 체크, 다음 갈 곳 조건 체크해서 dfs 재귀하면된다.
main 함수에서는 테스트 케이스도 입력 받으니 전체를 0으로 초기화 해주는 함수와 출력 값을 초기화 해주는 작업이 필요하다.
배열의 크기만큼 입력을 받은 후 배열을 돌며 배열이 1인 값과 방문하지 않은 곳을 dfs를 돌린다. dfs가 돌기 시작하면 연결되어 있는 모든 곳을 들리니 이 반복이 한번 끝나는 것이 의미하는게 한 컴포넌트이다. 그렇기에 dfs 다음 ret++을 하면 총 몇 개의 컴포넌트가 있는지 확인할 수 있다.

결과

후기

dfs 기본 문제라고 생각한다. 알고리즘을 알고 있다면 구현하는데 큰 무리없는 문제였다. 본인은 조금 헤맸다는게 함정...