80. C++ 백준 1012 번 유기농 배추 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 1012 번 유기농 배추 C++ 자세한 설명입니다.

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

1012번: 유기농 배추

 

먼저 백준 1012 번 C++ 정답 코드입니다.

#include <iostream>
#include <queue>
#define MAX 51
using namespace std;
int graph[MAX][MAX];
int x_dir[4] = {1, -1, 0, 0};
int y_dir[4] = {0, 0, 1, -1};
int M, N;

void BFS(int i, int j){
    queue<pair<int, int>> q;
    pair<int, int> loc;
    loc.first = i;
    loc.second = j;
    q.push(loc);
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++){
            int next_x = x + x_dir[d];
            int next_y = y + y_dir[d];
            if ( 0 <= next_x < M and 0 <= next_y < N ){
                if ( graph[next_x][next_y] == 1 ){
                    graph[next_x][next_y] = 0;
                    loc.first = next_x;
                    loc.second = next_y;
                    q.push(loc);
                }
            }
        }
    }
}

int main(){
    int T, K, x, y, cnt;
    cin >> T;
    for (int t = 0; t < T; t++){
        cnt = 0;
        cin >> M >> N >> K;

        //그래프 초기화
        for (int m = 0; m < M; m++){
            for (int n = 0; n < N; n++){
                graph[m][n] = 0;
            }
        }

        //입력
        for (int k = 0; k < K; k++){
            cin >> x >> y;
            graph[x][y] = 1;
        }

        //그래프
        for (int m = 0; m < M; m++){
            for (int n = 0; n < N; n++){
                if ( graph[m][n] == 1){
                    BFS(m, n);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

BFS 방식으로 구현해봤습니다.

BFS, DFS 둘 중 아무거나 사용하셔도 상관 없습니다.

배추근처에 지렁이가 한마리라도 있다면 인접한 배추를 이동하면서 연결된 배추들을 모두 지킬 수 있기 때문에 

배추 밭 전체를 탐색하면서 방문하지 않은 배추가 있으면 방문하여 지렁이 한마리를 배정해주고

DFS 혹은 BFS를 사용하여 연결된 모든 배추를 방문처리를 해주면

연결되지 않은 배추들 마다 지렁이 한 마리씩 배정이 됩니다.

 

위의 직관을 가지고 코드를 구현해 봅시다. 

 

Test Case 만큼 반복하고, 그래프, M, N, K 를 입력받습니다.

for (int t = 0; t < T; t++){
    cnt = 0;
    cin >> M >> N >> K;

    //그래프 초기화
    for (int m = 0; m < M; m++){
        for (int n = 0; n < N; n++){
            graph[m][n] = 0;
        }
    }

    //입력
    for (int k = 0; k < K; k++){
        cin >> x >> y;
        graph[x][y] = 1;
    }

그래프를 탐색하면서, 방문하지 않은 배추가 있다면 BFS 혹은 DFS를 진행해주고, 

배추 지렁이 한 마리씩 배정해줍니다.

//그래프
for (int m = 0; m < M; m++){
    for (int n = 0; n < N; n++){
        if ( graph[m][n] == 1){
            BFS(m, n);
            cnt++;
        }
    }
}

 

그래프의 모든 노드 방문이 끝나고 나면 지렁이 마리수를 출력해주면 됩니다.

cout << cnt << endl;

 

 

BFS는 다음과 같이 구현했습니다.

int graph[MAX][MAX];
int x_dir[4] = {1, -1, 0, 0};
int y_dir[4] = {0, 0, 1, -1};
int M, N;

void BFS(int i, int j){
    queue<pair<int, int>> q;
    pair<int, int> loc;
    loc.first = i;
    loc.second = j;
    q.push(loc);
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++){
            int next_x = x + x_dir[d];
            int next_y = y + y_dir[d];
            if ( 0 <= next_x < M and 0 <= next_y < N ){
                if ( graph[next_x][next_y] == 1 ){
                    graph[next_x][next_y] = 0;
                    loc.first = next_x;
                    loc.second = next_y;
                    q.push(loc);
                }
            }
        }
    }
}

여기서 BFS를 진행하면서 방문한 노드는 기존 1에서 0 으로 변경하여

다음번에 다시 방문하지 않도록 처리하였습니다. 

 

C++ 백준 1012 번 최종 코드입니다.

#include <iostream>
#include <queue>
#define MAX 51
using namespace std;
int graph[MAX][MAX];
int x_dir[4] = {1, -1, 0, 0};
int y_dir[4] = {0, 0, 1, -1};
int M, N;

void BFS(int i, int j){
    queue<pair<int, int>> q;
    pair<int, int> loc;
    loc.first = i;
    loc.second = j;
    q.push(loc);
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int d = 0; d < 4; d++){
            int next_x = x + x_dir[d];
            int next_y = y + y_dir[d];
            if ( 0 <= next_x < M and 0 <= next_y < N ){
                if ( graph[next_x][next_y] == 1 ){
                    graph[next_x][next_y] = 0;
                    loc.first = next_x;
                    loc.second = next_y;
                    q.push(loc);
                }
            }
        }
    }
}

int main(){
    int T, K, x, y, cnt;
    cin >> T;
    for (int t = 0; t < T; t++){
        cnt = 0;
        cin >> M >> N >> K;

        //그래프 초기화
        for (int m = 0; m < M; m++){
            for (int n = 0; n < N; n++){
                graph[m][n] = 0;
            }
        }

        //입력
        for (int k = 0; k < K; k++){
            cin >> x >> y;
            graph[x][y] = 1;
        }

        //그래프
        for (int m = 0; m < M; m++){
            for (int n = 0; n < N; n++){
                if ( graph[m][n] == 1){
                    BFS(m, n);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
    }

    return 0;
}

C++ 백준 1012 번 이었습니다. 감사합니다.