6주차(DFS와 BFS) - [C++]백준1012 유기농 배추

11 Apr 2022 in Study on Algorithm

백준1012 유기농 배추 링크

문제

예제 입력

---

코드

#include<iostream>
#include<queue>
using namespace std;

int t, m, n, k;
int cnt;
int map[50][50];
bool check[50][50];
// 방향 이동
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };

void dfs(int x, int y) {
    if (x < 0 || y < 0 || x >= n || y >= m) return;
    if (map[x][y] == 0 || check[x][y] == true) return; 
    check[x][y] = true;

    // 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출
    dfs(x - 1, y);
    dfs(x, y - 1);
    dfs(x + 1, y);
    dfs(x, y + 1);
}

void bfs(int x, int y) {
    queue<pair<int, int> > q;
    q.push({ x, y });
    check[x][y] = true;

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) { // 상, 하, 좌, 우 방향에 대해서  
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (map[nx][ny] == 1 && check[nx][ny] == false) {             
                    q.push({ nx,ny });
                    check[nx][ny] = true;
                }
            }  
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> m >> n >> k; // 가로y 세로x 배추

        for (int j = 0; j < k; j++) {
            int x, y;
            cin >> x >> y;
            map[y][x]=1;
        }

        for (int j = 0; j < n; j++) {
            for (int l = 0; l < m; l++) {
                if (check[j][l] == false && map[j][l] == 1) {
                    bfs(j, l);
                    //dfs(j, l);
                    cnt++;
                }
            }
        }
        cout << cnt << "\n";
        // #include<algorithm> fill(&map[0][0], &map[50][50], 0); - 2차원 배열 0으로 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                check[i][j] = false;
                map[i][j] = 0;
            }
        }
        cnt = 0;
    }
}

설명

이 문제는 농장에 유기농 배추를 키우기 위해서 뭉쳐있는 곳에 배추흰지렁이를 얼마나 배치해야 하는지 구하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 Queue를 사용하여 구현했습니다. 농장의 크기와 배추 수를 입력 받고 0, 0부터 배추가 있는 구역인지 확인하며 있다면 BFS 또는 DFS를 변형하여 두 가지 경우로 구현했습니다. BFS는 너비우선 탐색으로 나선형 모습으로 탐색을 하고 DFS는 깊이우선 탐색으로 특정 방향으로 나가는 모습으로 탐색을 합니다. 그리고 check값을 배정하는데 이것은 같은 곳을 탐색할 수 있는 것을 방지합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과