백준 1012 유기농 배추 c++ [컴공과고씨]

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

1012번: 유기농 배추

문제를 읽었을 때 사용해야할 알고리즘이 떠오른것은 그래프 탐색이였다.

그 중 나는 넓이 우선 탐색 bfs를 선택해서 풀었다.

전체적인 풀이 방법은 배추가 있는 한 곳에 지렁이를 풀어준다. 그리고 그 지렁이가 인접해 있는 배추를 탐색하기 시작 한다. 이때 지렁이가 지나간 곳은 bool visit로 해서 방문했다는 표시를 해준다. 그리고 bfs가 끝나고 다른 배추 위치를 bfs에 넣어 지렁이를 다시 푸는데 이때 방문했다는 표시가 있으면 지렁이를 넣지 않는다. 만약 배추를 방문하지 않았다면 지렁이를 넣어준다. 즉 bfs에 배추의 위치를 넣어주는 것이다. 이때 지렁이를 넣었기 때문에 카운트를 하나 올려준다.

이렇게 해서 모든 배추 위치를 검사하면 몇마리의 지렁이가 필요한지 나오게 된다. 

 

각 코드에 대한 설명이다. 

 

테스트 케이스가 여러개 이므로 새로운 테스트를 할때마다 map, 방문여부, 카운트를 초기화 해주는 함수 이다.\

 

bfs구현은 먼저 배추 좌표가 들어오면 큐에 넣어준다. 큐가 빌때까지 반복해준다.

여기서 n_x와 n_y 배추에 지렁이가 있으면 인접한 배추 상하좌우로 움직일 수 있기 때문에

반복문으로 상하좌우로 지렁이를 움직여준다. 이때 다음 좌표가 map안에 있어야하고 

다음 좌표가 이전에 방문을 하지 않아야하며 , 배추가 있는 좌표인 것을 조건문을 통해 만들어주었다.

그 후 큐에 넣어주고 방문기록을 해주면 bfs 완성이다.

 

main 함수

여기서는 배추 위치를 기록하여서 배추 위치를 bfs에 넣어줄건데 이 때 이미 지렁이가 지나간 자리는 넣어줄 필요가 없기 때문에 조건문으로 처리해준다. 그리고 bfs에 배추 위치를 넣는 것은 지렁이를 푸는 것이니까 카운트를 해준다.

 

전체 코드

#include <iostream>
#include <queue>
#include <string.h>
#include <vector>
using namespace std;
int t, m, n, k, a, b, cnt;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int map[51][51];
bool visit[51][51];
queue<pair<int, int>> bfs_q;
void make_empty(){
    memset(map, 0, sizeof(map));
    memset(visit, false, sizeof(visit));
    cnt = 0;
} // 초기화 하는 함수
void bfs(int a1, int b1){
    bfs_q.push(make_pair(a1, b1));
    while(!bfs_q.empty()){
        int x = bfs_q.front().first;
        int y = bfs_q.front().second;
        
        bfs_q.pop();
 
        for (int i = 0; i < 4; i++){
            int n_x = x + dx[i]; //상하좌우로 이동한 다음 x좌표
            int n_y = y + dy[i]; //상하좌우로 이동한 다음 y좌표
            if(n_x < m && n_x>=0 && n_y <n && n_y >=0){ // 다음 좌표가 map안에 있어야함.
                if(map[n_x][n_y] == 1 && !visit[n_x][n_y]){//방문을 하지않았고, 배추가 있는 좌표인 경우만
                    bfs_q.push(make_pair(n_x, n_y));
                    visit[n_x][n_y] = true;
                }
            }
        }
    }
}
int main(){
    vector<int> result;
    cin >> t;
    for (int T = 0; T < t;T++){
        make_empty(); // 초기화
        cin >> m >> n >> k;
        queue<pair<int, int>> q;
        for (int i = 0; i < k;i++){
            cin >> a >> b;
            q.push(make_pair(a, b)); //배추가 있는 위치 기록
            map[a][b] = 1;
        }
        while(!q.empty()){ //배추 위치를 다 검사 할때 까지
            int temp1 = q.front().first;
            int temp2 = q.front().second;
            q.pop();
            if(!visit[temp1][temp2]){// 지렁이가 있는 배추에 인접하지 않은 배추만 넣어줌
                cnt++; //지렁이 카운트
                bfs(temp1, temp2);
            }
        }
        result.push_back(cnt); // 결과 값 저장
    }
    for (int i = 0; i < result.size();i++){
        cout << result[i] << '\n';
    }
        return 0;
}

 

사용 알고리즘 bfs

 

yea!