[백준] 1012번: 유기농 배추(BFS) - C++

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

1012번: 유기농 배추

---

#include <iostream>
#include <queue>
using namespace std;

int M,N,K;
int map[50][50];
bool visited[50][50];
queue<pair<int,int>> q;
int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}};

void reset(int M, int N)
{
    for(int y=0; y < N;y++)
        for(int x = 0;x < M;x++)
        {
            map[y][x] = 0;
            visited[y][x] = 0;
        }
}

void BFS(int y, int x)
{
    visited[y][x] = true;
    q.push(pair<int,int>(y,x));
    while(!q.empty())
    {
        y = q.front().first;
        x = q.front().second;
        q.pop();
            
        for(int d = 0;d<4;d++)
        {
            int ny = y+dir[d][0];
            int nx = x+dir[d][1];
                     
            if(( ny >= 0 && nx >= 0) && (ny < N && nx < M))
            {
                if(map[ny][nx] == 1 && !visited[ny][nx])
                {
                    visited[ny][nx] = true;
                    q.push(pair<int, int>(ny, nx));
                }
            }
        }
    }
}

int main()
{
    int T;
    
    cin >> T;
    for(int i = 0;i < T;i++)
    {
        cin>>M>>N>>K;
        reset(M,N);
        
        for(int k=0;k<K;k++)
        {
            int x,y;
            cin>>x>>y;
            map[y][x] = 1;
        }
        
        int result = 0;
        for(int y=0;y<N;y++)
        {
            for(int x = 0;x<M;x++)
            {
                if(!visited[y][x] && map[y][x]==1)
                {
                    BFS(y,x);
                    result++;
                }
            }
        }
        cout<<result<<endl;
    }

    return 0;
}

BFS로 문제를 해결하였다. 

BFS 문제를 풀 때, 코드의 기본 구성은 비슷한데 특정 자료구조 하나씩이 다른 것 같다.

미로찾기 문제에서는 dist배열이, 여기서는 result가 답을 구하는데 큰 역할을 한다.

 

이 문제에서는 특정 조건에서 반복적으로 BFS 함수를 호출하였다.

먼저 map배열의 index가 작은 것부터 확인하면서, 방문하지 않았고 배열의 값이 1인 경우에만

BFS함수를 호출하여 인접한 배추들을 탐색한다. 이 때, result의 값을 증가시켜 최종 값을 구한다.

 

처음에는 M, N이 가로인지 세로인지 정확하게 확인하지 않아 틀렸다.

index값을 잘 확인해야겠다!!!!