[BOJ] 1012 - 유기농 배추

황규빈·2022년 1월 23일
0

알고리즘

목록 보기
15/33

💎 문제


차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 1 1 0 0 0 1 1 1
0 0 0 0 1 0 0 1 1 1

💎 입력


입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

💎 출력


각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

💎 풀이 방법


이제 살짝 실버 구간과 골드 5 사이 구간의 백준 BFS문제들을 거의 진짜 똑같은 것 같다. 다른 문제들과 굉장히 유사하게 풀었고 어렵지 않은 문제였다!!

먼저 주의 해야할 점은 역시 역시 상하좌우의 내용들이 1인지 검사하고 queue에 넣어준 뒤 이동하여서 다시 검색하는 너비 우선 탐색이기 때문에 상하좌우의 정확한 인덱스가 들어갔는지 확인해야하였다. 또한 BFS가 한번 탐색될 때마다 배추 흰 지렁이의 마릿수를 추가해주는 것을 유의하면은 그렇게 어렵지 않았다. 범위도 그렇게 크지 않은 배열이였기 때문에 DFS를 사용하여도 쉽게 풀 수 있을 문제라고 생각된다.

void BFS(int v[50][50], int Ty, int Tx){
    
    queue<pair<int, int>> q;
    q.push({Tx, Ty});
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        visited[Ty][Tx] = true;
        q.pop();
        for(int i = 0;i < 4;i++){
            int tempX = x + X[i];
            int tempY = y + Y[i];
            if(tempX >= 0 && tempY >= 0 && tempX < M && tempY < N && visited[tempY][tempX] == false && v[tempY][tempX] == 1){
                q.push({tempX, tempY});
                visited[tempY][tempX] = true;
            }
        }
    }
}

함수 BFS만 간단하게 또 살펴보자면 배열과 탐색하는 위치의 인덱스를 매개변수로 받아서 이를 queue를 사용하여 상하좌우 중 탐색하지 않은 곳이 1의 값이라면 queue에 push해 주어 BFS를 완료해주었다.

아참 그리고 테스트케이스가 여러개가 올 수 있기 때문에 배열과 탐색여부를 확인하는 visited 배열을 초기화해주는 것을 잊지말아야한다!!

💎 전체 코드


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int T, M, N, K;
int X[4] = {0, 1, 0, -1};
int Y[4] = {-1, 0, 1, 0};
bool visited[50][50];

void BFS(int v[50][50], int Ty, int Tx){
    
    queue<pair<int, int>> q;
    q.push({Tx, Ty});
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        visited[Ty][Tx] = true;
        q.pop();
        for(int i = 0;i < 4;i++){
            int tempX = x + X[i];
            int tempY = y + Y[i];
            if(tempX >= 0 && tempY >= 0 && tempX < M && tempY < N && visited[tempY][tempX] == false && v[tempY][tempX] == 1){
                q.push({tempX, tempY});
                visited[tempY][tempX] = true;
            }
        }
    }
}

int main(int argc, const char * argv[]) {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int result = 0;
    cin >> T;
    
    for(int i = 0;i < T;i++){
        cin >> M >> N >> K;
        int v[50][50] = { 0 };
        
        for(int i = 0;i < 50;i++){
            for(int j = 0;j < 50;j++){
                visited[i][j] = false;
            }
        }
        for(int i = 0;i < K;i++){
            int x, y;
            cin >> x >> y;
            v[y][x] = 1;
        }
        
        for(int i = 0;i < N;i++){
            for(int j = 0;j < M;j++){
                if(v[i][j] == 1 && visited[i][j] == false){
                    BFS(v, i, j);
                    result++;
                }
            }
        }
        
        cout << result << "\n";
        result = 0;
    }
    
    return 0;
}

💎 고민


사실 알고리즘 풀고서 블로그에 글을 쓸지 말지 고민했었는데 이전에 풀었던 BFS문제와 굉장히 유사하고 내용만 달라서 그랬다,, 그래도 이번 것을 마지막으로 좀 다양한 내용이 섞여있는 그래프 탐색 문제를 풀어보도록 해볼려구 한다!! 이제 진짜 그래프 탐색이 익숙해지는 것 같당!! 열심히하자!!

화이팅~!!

profile
안녕하세욤

0개의 댓글