[알고리즘] 1012번: 유기농 배추

0. 문제

 

1012번: 유기농 배추

 

---

1. 문제 이해

 

 

주어진 맵에서 덩어리의 개수를 알아내면 된다.

 

이런 덩어리를 연결된 컴포넌트(connected component)라고 한다.

 

1. 연결된 노드를 탐색한다. 그리고 배제한다. → DFS, BFS 사용.

 

https://ko.wikipedia.org/wiki/플러드_필

---

2. 제출

 

가. a[][], visited[][]를 전역 변수로 선언

//백준 1012: 유기농 배추
#include <iostream>
#include <cstring> // memeset

using namespace std;

const int max_n = 50;
const int max_m = 50;
const int dy[] ={-1, 0, 1, 0};
const int dx[] ={0, 1, 0, -1};
int a[max_n][max_m], visited[max_n][max_m];
int t, n, m, k;

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> t;
    for(int test_case = 1; test_case <= t; test_case++){
        int ret = 0;
        memset(a, 0, sizeof(a)); 
        memset(visited, 0, sizeof(visited));
        cin >> m >> n >> k;
        for(int i=0; i<k; i++){
            int x, y;
            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]){
                    ret++; 
                    dfs(i,j);
                }
            }    
        }
        cout << ret << "\n";
    }

    return 0;
}

• memset(a, 0, sizeof(a)); memset(visited, 0, sizeof(visited)); : 이차원 a와 visited를 0으로 배열 초기화.

 

---

나. a[][], visited[][]를 지역 변수로 선언

//백준 1012: 유기농 배추
#include <iostream>

using namespace std;

const int max_n = 50;
const int max_m = 50;
const int dy[] ={-1, 0, 1, 0};
const int dx[] ={0, 1, 0, -1};
int t, n, m, k;

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> t;
	for(int test_case = 1; test_case <= t; test_case++){
		int ret = 0;
		int a[max_n][max_m], visited[max_n][max_m];
		fill(&a[0][0], &a[0][0] + max_n * max_m, 0);
		fill(&visited[0][0], &visited[0][0] + max_n * max_m, 0);
		cin >> m >> n >> k;
		for(int i=0; i<k; i++){
			int x, y;
			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]){
					ret++; 
					dfs(i,j,a,visited);
				}
			}	
		}
		cout << ret << "\n";
	}

	return 0;
}

• void dfs(int y, int x, int a[][max_m], int visited[][max_m]){ 또는 void dfs(int y, int x, int a[max_n][max_m], int visited[max_n][max_m]){로 이차원 배열을 매개변수로 선언.

 

---