coding-test

<백준> 1012번 유기농 배추 / C++ 풀이

도멩 2024. 1. 7. 15:09

중점:

1. bfs 알고리즘 사용

2. 행렬에서 시작점 파악 후 queue에 push

3. 시작점 파악 시에 방문 여부, 배추가 심어져 있는지 확인

 


정답 코드:

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second

int m, n, k;
int board[52][52];
bool vis[52][52];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue <pair<int, int> > Q;

void bfs(int x, int y){
    vis[x][y] = true;
    Q.push({x, y});

    while (!Q.empty())
    {
        auto cur = Q.front();
        Q.pop();

        for(int dir = 0; dir < 4; dir++){
            int nx = cur.X + dx[dir];
            int ny = cur.Y + dy[dir];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(vis[nx][ny] || board[nx][ny] != 1) continue;

            vis[nx][ny] = true;
            Q.push({nx, ny});
        }
    }   
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;

    cin >> t;

    while(t--){
        cin >> m >> n >> k;

        int x, y;
        int count = 0;

        for (int i = 0; i < k; i++){
            cin >> x >> y;
            board[y][x] = 1;
        }

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if(board[i][j] == 1 && !vis[i][j]){
                    bfs(i, j);
                    count++;
                }
            }
        }

        cout << count << "\n";

        for (int i = 0; i < n; i++){ //테스트 케이스 반복을 위해서 초기화 작업 진행
            fill(board[i], board[i] + m, 0);
            fill(vis[i], vis[i] + m, false);
        }
    }
}