[BOJ / C++] #1012 유기농 배추

🥬 문제 링크

🥬 문제풀이

map에서 서로 인접한 배추 그룹의 개수를 세주는 문제이다.
BFS로 구현하였고, 이미 방문한 것은 따로 visited배열 없이 map[i][j]=2로 만들어 진행했다.

1. 입력 받기
2. 맵을 완전탐색하면서 map[i][j]==1 (배추가 있는 곳)이 나오면 bfs(i,j)실행해주기.
3. bfs
   • i,j좌표를 큐에 삽입, map[i][j]=2로 만들어줌으로써 방문했음으르 표시
   • while(!q.empty())로 인접한 것들을 모두 삽입해주며 bfs실행
   • bfs 함수를 빠져나오고 나면, 하나의 배추 그룹을 센 것이므로 cnt++

🥬 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define MAX 51
int map[MAX][MAX];
int M, N, K;

//상우하좌
int dr[4]={-1,0,1,0};
int dc[4]={0,1,0,-1};


void bfs(int i, int j){
    queue<pair<int,int>> qq;
    qq.push(make_pair(i,j));
    map[i][j]=2; //이미 방문한 곳은 2로 만들어주기.

    while(!qq.empty()){
        int r=qq.front().first;
        int c=qq.front().second;

        qq.pop();

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

            if(nr<0||nr>N-1||nc<0||nc>M-1||map[nr][nc]!=1) continue;

            qq.push(make_pair(nr,nc));
            map[nr][nc]=2;
        }
    }
}

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

    for(int t=0;t<T;t++){

        memset(map,0,sizeof(map));

        int cnt=0;
        cin>>M>>N>>K;

        for(int i=0;i<K;i++){
            int c, r;
            cin>>c>>r;
            map[r][c]=1;
        }

        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                if(map[i][j]==1) {
                    bfs(i,j);
                    cnt++;
                }
            }
        }
        cout<<cnt<<"\n";
    }
}

45' : bfs에서 계속 메모리 오류가 났다. pop하고 나서야 방문했다고 표시했기 때문 push할 때 표시해주기.