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

https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

입력 
T : 밭의 수 
M,N : 밭의 크기 MxN 
K : 배추가 심어진 개수 
K번 입력받음 


메인함수()
T만큼 반복 
M,N : 밭의 크기 MxN 
K : 배추가 심어진 개수 
K번 만큼 입력받음 
반복문으로 map 채우기 
BFS() 

 

BFS 함수()
방문한 곳 표시 
큐에 현재 위치 넣기 
큐가 비어있지 않는 동안 반복
현재 위치 넣기 
큐에서 현재 위치 pop
상 하 좌 우 확인 1
있으면 큐에 넣기 

#include <iostream>
#include <algorithm>
#include <queue>
#include <utility>


using namespace std; 

int t;
int n,m;
int k;
int cnt=0;
int map[51][51]={0,};
int visit[51][51]={0,};

int x[4] = {0,0,1,-1};
int y[4] = {1,-1,0,0};

void init() //초기화 위함
{
    cnt =0;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            map[i][j] = 0;
            visit[i][j] = 0;
        }
    }
}
void bfs(int s1, int s2)
{
    queue <pair <int,int>>q;
    
    q.push(make_pair(s1,s2));
    visit[s1][s2] = 1;
    
    while(!q.empty())
    {
        pair<int,int> now = q.front();
        q.pop();
        
        for(int i=0;i<4; i++)
        {
            int py = now.first+y[i];
            int px = now.second  + x[i];
            if(0<= py & py < n & 0<= px & px < m & visit[py][px] == 0 & map[py][px] == 1){
                visit[py][px] = 1;
                
                q.push(make_pair(py,px));
            }
        }
        
    } 
    
}
int main()
{
    cin >> t;
    int x,y;
    while(t>0)
    {
        cin >> m >>n>>k;
        init();
        
        for(int i=0; i<k; i++)
        {
            cin >>x>>y;
            map[y][x]=1;
        }
        
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(map[i][j]==1 && visit[i][j]==0)
                {
                    bfs(i,j);
                    cnt++;
                }
            }
        }
        cout << cnt <<endl;
       
        t--;
        
    }
    
    
    return 0;
}

 

DFS로도 풀어보기