백준 1012 유기농 배추 / C++

문제 : 1012

풀이 point

배추 밭은 기본 0으로 초기화 해놓은 뒤 배추가 놓이는 좌표만 1로 세팅해준다.
이 배추 밭을 통해 bfs를 수행하여 지렁이가 놓일 갯수를 체크한다.

풀이 방법

좌표가 중요하다. 자꾸 틀림이 뜨면 범위가 이상한 것이니 한번씩 확인해봐야한다.

코드

//백준 1012, 유기농 배추

#include <iostream>
#include <queue>

int grid[51][51];
int N, M;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void bfs(int i, int j){
    std::queue<std::pair<int, int>> q;
    grid[i][j] = 0;
    q.push({i, j});
    while(!q.empty()){
        auto curr = q.front(); q.pop();
        for(int k{0}; k<4; ++k){
            int nx = curr.first + dx[k];
            int ny = curr.second + dy[k];
            if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
            if(grid[nx][ny] != 1) continue;
            
            grid[nx][ny] = 0;
            q.push({nx, ny}); 
        }
    }
}

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

    int T, K;
    std::cin >> T;

    while(T--){
        int cnt = 0;
        std::cin >> M >> N >> K;
        for(int i{0}; i<M; ++i){
            for(int j{0}; j<N; ++j){
                grid[i][j] = 0;
            }
        }
        for(int k{0}; k<K; ++k){
            int x, y;
            std::cin >> x >> y;
            grid[x][y] = 1;
        }
        for(int i{0}; i<M; ++i){
            for(int j{0}; j<N; ++j){
                if(grid[i][j] == 1){
                    ++cnt;
                    bfs(i, j);
                }
            }
        }
        std::cout << cnt << '\n';
    }
    return 0;
}

사족

자꾸 틀렸다고 떠서 미치는 줄 알았다... 범위가 이상한 것이던데 솔직히 왜인지를 잘 모르겠다... chatgpt도 못찾더라 ㅋㅋ

2025-02-05T10:12:31.683Z