[BOJ알고리즘, C++]#1012_유기농 배추, 그래프 탐색, BFS, 영역 찾기

 

#1. 문제

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

1012번: 유기농 배추

 

---

 

#2. 풀이

 

1. 그래프 탐색, BFS

https://webddevys.tistory.com/291#%232.%20%ED%83%90%EC%83%89-1

[자료구조]#6_그래프

 

BFS(너비 우선 탐색)은 그래프의 모든 정점을 탐색하는 방법 중 하나로, 현재 정점과 인접한 정점들을 우선적으로 탐색하며, 최종적으로 모든 정점을 탐색하는 알고리즘입니다. 일반적으로, BFS는 큐 자료구조를 활용하여 구현합니다.

 

2. 일반적인 영역 찾기 문제, 방문 여부 기억하자!

 

1. 먼저, 배추밭의 모든 위치를 순회하며, "1" 값을 갖는, 즉 배추가 심어져 있는 위치를 출발점으로 BFS를 수행합니다.
2. 이때, 각 BFS는 그 수행과정에서 이미 방문한 위치들에 대하여 방문여부를 체크하고, 이후 다음 위치에서 수행할 BFS 과정에서 이미 방문한 위치들을 다시 방문하는 것을 방지해 줍니다.
3. 그리고, 각 BFS를 모두 성공적으로 끝마치고, 배추 흰 지렁이 개수를 +1 씩 카운트해줍니다.

 

---

 

#3. 코드

 

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

typedef pair<int, int> p;

int T, N, M, K, swarm;
int dy[] = {1, -1, 0, 0};
int dx[] = {0, 0, 1, -1};

void bfs(p start, vector<vector<int>> &farm, vector<vector<bool>> &visited)
{
    // 큐 선언
    queue<p> q;

    q.push(start);
    visited[start.first][start.second];

    while (!q.empty())
    {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; ++i)
        {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx] || farm[ny][nx] == 0)
                continue;

            visited[ny][nx] = true;
            q.push({ny, nx});
        }
    }
    // 지렁이 개수 추가
    swarm++;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> T;

    while (T--)
    {
        cin >> M >> N >> K;

        // 2차원 vector 형식의 배추 밭, 2차원 vector 형식의 방문 여부 체크
        vector<vector<int>> farm(N, vector<int>(M));
        vector<vector<bool>> visited(N, vector<bool>(M, false));

        while (K--)
        {
            int X, Y; // X 는 행, Y는 열

            cin >> X >> Y;
            farm[Y][X] = 1;
        }

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < M; ++j)
                if (!visited[i][j] && farm[i][j] == 1)
                    bfs({i, j}, farm, visited);

        cout << swarm << '\n';

        swarm = 0;
    }

    return 0;
}

 

---