[백준/1012번][C++] 유기농 배추

www.acmicpc.net/problem/1012

1012번: 유기농 배추

BFS를 통해 문제를 해결했다.

 

주의할 점 2가지가 있는데

1. 가로, 세로 인덱스가 반대로 되어 있다.

2. 각 테스트 케이스마다 보드를 초기화 해 주어야 한다.

 

나는 1, 2번으로 인해 시간을 굉장히 오래 잡아먹었다. 

다른 요소들은 그냥 보통의 BFS에 count를 더한 것이다.

#include<iostream>
#include<queue>

using namespace std;

#define X first
#define Y second
int n,m,k,t;
int board[52][52];
int vis[52][52];
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};

int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    for(int i=0;i<t;i++){
        for(int i=0;i<51;i++){
            for(int j=0;j<51;j++){
                board[i][j]=0;
                vis[i][j]=0;
            }
        }
        cin>>m>>n>>k;
        for(int j=0;j<k;j++){
            int a,b;
            cin>>a>>b;
            board[a][b]=1;
        }
        int count=0;

        for(int p=0;p<m;p++){
            for(int q=0;q<n;q++){
                if(vis[p][q]||board[p][q]!=1) continue;
                count++;
                queue<pair<int,int>> Q;
                vis[p][q]=1;
                Q.push({p,q});
                while(!Q.empty()){
                    pair<int,int> 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||ny<0||nx>=m||ny>=n) continue;
                        if(board[nx][ny]!=1||vis[nx][ny]) continue;
                        vis[nx][ny]=1;
                        Q.push({nx,ny});
                    }
                }
            }
        }
        cout<<count<<"\n";
    }
}

입력1

 

출력1

입력2

출력2