백준 1012. 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

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

int M, N, K;
int cnt = 0;
int cab[51][51];
bool mark[51][51];
int dc[4] = {0, 1, 0, -1};
int dr[4] = {-1, 0, 1, 0};

void dfs(int r, int c) {
    if(mark[r][c] || cab[r][c] == 0) return;
    mark[r][c] = true;

    for(int i = 0; i < 4; i++) {
        int nr = r + dr[i];
        int nc = c + dc[i];

        if(nr < 0 || nr > N || nc < 0 || nc > M) continue;

        dfs(nr, nc);
    }
}


void init() {
    cnt = 0;
    fill(&cab[0][0], &cab[51][51], 0);
    fill(&mark[0][0], &mark[51][51], false);
}

int main() {
    int T;
    cin >> T;

    while(T--) {
        cin >> M >> N >> K;

        for(int i = 0; i < K; i++) {
            int x, y;
            cin >> x >> y;
            cab[y][x] = 1;
        }

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(!mark[i][j] && cab[i][j] == 1) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
        init();
    }

}

 

특이했던 점은 데이터를 배열처럼 주지않고 x,y좌표로 주기 때문에 주의해야 한다. 

데이터를 배열에 저장할때 arr[x][y] 이런식으로 하지않고 arr[y][x] 이런 식으로 저장하면 일반 배열 풀때처럼 풀수있다.