백준 1012 - 유기농 배추(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

BFS 문제였습니다. 

문제 조건

출력 예시

 

문제 접근 방법

1. 배추들의 좌표를 입력받은뒤, 배열에 배추의 존재여부를 표시한다.

2. For문을 통해서 배추가 존재하면서, 전에 방문하지 않았던 곳을 찾아 BFS를 실행한다.

3. 필요한 지렁이의 갯수를 출력한다.

4. Test_case 만큼 반복한다.

 

 

문제 접근 방법 - 1번

        for (int i = 0; i < K; i++) {
            int x, y;
            cin >> x >> y;
            vet[y + 1][x + 1] = 1;
        }

X,Y 좌표이기에, 배열에 저장할 때는 Y, X로 저장해야합니다!!

 

문제 접근 방법 - 2번 - BFS

void bfs(int a, int b) {
    queue<qu> q;
    q.push({ a,b });
    while (!q.empty()) {
        int x1 = q.front().x;
        int y1 = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x1 + arr[i];
            int yy = y1 + arr2[i];
            if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
                if (check[xx][yy] == 0 && vet[xx][yy] == 1) {
                    check[xx][yy] = 1;
                    q.push({ xx,yy });
                }
            }
        }
    }
}

배추의 좌표를 (a, b)로 받았습니다. 이를 구조체 큐에다가 저장한 다음, check[a][b]에 방문 표시를 했습니다. 

큐를 통해서 X, Y 좌표를 받은 뒤, 4방향 탐색을 해줬습니다. 좌표의 범위에 맞고, 이전에 방문하지 않았으며, 배추가 있는 곳이라면, 방문 표시를 한후, 큐에 해당 좌표를 넣어줘서 다시 탐색을 돌 수 있게 했습니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

int test_case, M, N, K;
int vet[51][51];
int check[51][51];
int arr[4] = { 0,1,0,-1 };
int arr2[4] = { 1,0,-1,0 };
typedef struct qu {
    int x;
    int y;
}qu;

void bfs(int a, int b) {
    queue<qu> q;
    q.push({ a,b });
    while (!q.empty()) {
        int x1 = q.front().x;
        int y1 = q.front().y;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int xx = x1 + arr[i];
            int yy = y1 + arr2[i];
            if (xx >= 1 && xx <= N && yy >= 1 && yy <= M) {
                if (check[xx][yy] == 0 && vet[xx][yy] == 1) {
                    check[xx][yy] = 1;
                    q.push({ xx,yy });
                }
            }
        }
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> test_case;
    for(int k = 0; k < test_case; k++){
        int number_warm = 0;
        cin >> M >> N >> K;
        for (int i = 0; i < K; i++) {
            int x, y;
            cin >> x >> y;
            vet[y + 1][x + 1] = 1;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (vet[i][j] == 1 && check[i][j] == 0) {
                    number_warm++;
                    check[i][j] = 1;
                    bfs(i, j);
                }
            }
        }
        memset(check, 0, sizeof(check));
        memset(vet, 0, sizeof(vet));
        cout << number_warm << "\n";
    }
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!