백준온라인저지(BOJ)/#1012/유기농 배추

유기농 배추 문제이다.

문제에서 밭이 있으면, 1로 칠해진 밭끼리 끊어지지 않고 연결된 연결 고리(?) 집합이 몇 개 인지 구하면 된다. 

dfs로 풀 수 있는데, 다만 동서남북 좌표로 dfs를 탐색한다고 보면 된다. 

주황색으로 동그라미 친 포인트를 시작점이라고 할 때 동서남북, 4번 반복하면서 시작포인트와 인접한 포인트가 1인 지점을 발견한다면, 거기로 포인트를 옮기고, 옮긴 포인트를 Argument(인자)로 dfs를 재귀 호출해준다. 

#include <vector>
#include <iostream>

using namespace std;
vector<vector<int>> board;

int M, N, K, x, y;
const int dy[] = {0, 0, -1, 1};
const int dx[] = {-1, 1, 0, 0};

void dfs(int y, int x){
    board[y][x] = -1;
    for(int m = 0; m < 4; m++){
        //board[next_y][next_x]는 먼저 next_y ,next_x 좌표의 범위를 설정하고 다음줄에 꼭 적어야함
        if((y+dy[m])>=0 && (y+dy[m]<N)
           &&(x+dx[m])>=0 && (x+dx[m]<M)
           &&(board[y+dy[m]][x+dx[m]]==1)){
            dfs(y+dy[m],x+dx[m]);
        }
    }
}

int main(){
    int T;
    cin>>T;
    while(T--){
        cin>>M>>N>>K;
        board.resize(N,vector<int>(M,0)); // 2-Dimensional Vector Initialization
        for(int k = 0; k < K; k++){
            int a, b;
            cin>>a>>b;
            //y,x를 거꾸로 받으므로 b, a순으로 board[][]에 입력해야 한다.
            board[b][a] = 1;
        }
        int cnt = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < M; j++){
                if(board[i][j]==1){
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        cout<<cnt<<endl;
        board.clear();
    }
    return 0;
}

구현 코드는 아래와 같으며, 통상적으로 프로그래밍에서 x,y좌표는 y, x로 거꾸로 쓰는 경우가 많으므로 이 점을 유의해서 작성하자.