백준 | 1012. 유기농 배추

 

1. idea 

• 입력 순서가 가로, 세로, 배추 위치의 개수니까 vector를 전부 0으로 만들고 입력받은 배추 위치만 1로 바꾸기
• vector돌면서 배추 만나면 dfs, dfs 내에서 인접한 배추들 싹 돌고, 0으로 바꾸기(방문표시)
• 배추 흰 지렁이 개수 ++
• 배추 흰 지렁이 개수 cout

 

2 DFS 함수 만들기

void dfs(vector<vector<int>>&map, int x, int y, int ex, int ey){
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};
    map[y][x] = 0;
    
    for(int i =0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx >= 0 && nx < ex && ny >= 0 && ny < ey){
            if(map[ny][nx]) dfs(map, nx, ny, ex, ey);
        }
    }
}

 

3. 전체 지도 순회

        int cnt = 0;
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                if(map[i][j]){
                    dfs(map, j, i, C, R);
                    cnt++;
                }
            }
        }

 

4. 코드 전문

 

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

void dfs(vector<vector<int>>&map, int x, int y, int ex, int ey){
    int dx[] = {0, 0, -1, 1};
    int dy[] = {1, -1, 0, 0};
    map[y][x] = 0;
    
    for(int i =0; i<4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx >= 0 && nx < ex && ny >= 0 && ny < ey){
            if(map[ny][nx]) dfs(map, nx, ny, ex, ey);
        }
    }
}

int main(){
    int T, C, R, X;
    cin >> T;
    while(T--){
        cin >> C >> R >> X;
        vector<vector<int>>map(R, vector<int>(C,0));
        int c, r;
        while(X--){
            cin >> c >> r;
            map[r][c] = 1;
        }

        int cnt = 0;
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                if(map[i][j]){
                    dfs(map, j, i, C, R);
                    cnt++;
                }
            }
        }

        cout << cnt << endl;
    }
    
    return 0;
}