[C++/BOJ]백준 1012 유기농배추(BFS) 알고리즘 문제풀이

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

 

1012번: 유기농 배추

 

BFS, DFS의 기본문제인 실버2 유기농 배추이다.

 

BFS의 기초만 알고있다면 쉽게 풀수있다.

 

바킹독님 코드를 보며 공부했기때문에 코드는 갓킹독님의 BFS의 풀이와 유사할것이다.

 

예제 입력값을 표로 나타낸것

예제 입력과 출력값

< 코드 >

#include<iostream>
#include<queue>
#define x first
#define y second 
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
using namespace std;
int main(){
    queue<pair<int,int> >Q; 
    int t;
    cin >> t;
    while(t--){
        int vis[51][51] = {}; //0으로 초기화
        int board[51][51] = {}; // 0으로 초기화
        int n,m,k;
        cin >> n >> m>>k;
        for(int i=0;i<k;i++){
            int a,b;
            cin >> a>> b;
            board[a][b] = 1; //입력받은곳에 양배추가 있으므로
        }
        int ans = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(board[i][j]==0 || vis[i][j] == 1) continue; // 양배추가 없거나 이미 방문한곳이면 for문의 다음조건으로 
                Q.push({i,j});
                vis[i][j] =1;
                ans++; // 개수를 증가시킨다
                while(!Q.empty()){ //주변에 양배추가 있는곳의 vis를 모두 1으로 만들어준다.
                    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(board[nx][ny]!=1 || vis[nx][ny] != 0) continue;
                        Q.push({nx,ny});
                        vis[nx][ny] =1;
                    }
                }
            }
        }
        cout<< ans<<"\n";
    }
    
}

 

문제풀이

위 그림처럼 예제의 표에서 함께 있는 1의 개수를 세어주면된다.

즉 위 표에서 1은 5개가 있으므로 5개를 출력하면 된다.

 

1) 가로길이, 세로길이, 배추의 개수를 입력받는다.

 

2) 입력받은 배추의 개수만큼 a,b를 입력받아 board에 배추가 있음을 표시한다.

 

3) 아래 코드와 같이 이중 for문을 사용하여 배추가 있고 방문하지 않은곳을 찾는다.

 

 

- 처음으로 배추를 찾은 곳을 큐에 넣어준다.

 

ans는 배추가 모여있는곳을 저장하는 변수이다. 1을 증가시켜 개수를 셀수있도록 한다.

 

방문했음을 vis[i][j] = 1로 알린다.

 

 

4) 큐에 넣어진 곳을 nx와 ny를 이용하여 탐색한다.

 

범위를 벗어났거나 배추가 없거나 방문했던곳이면 continue를 한다.

 

5) 그후 ans를 출력해주면 답이다.

요약 

queue에 넣은 1 주변의 모든 1을 방문한것으로 만들어 한번 방문한 1의 무리는 다시 방문하지 않게한다.

 

queue에 들어갈때마다 ans를 증가시켜 1 무리의 숫자를 저장하고 모든 탐색이 끝난후 출력한다.