BOJ : 1012번 유기농 배추[C++][DFS]

1012번 유기농 배추 문제 풀이에 관한 포스팅입니다.

1012번 : 유기농 배추

최근에 풀이한 문제 중 초기 계획과 거의 똑같게 구현한 문제가 있어 포스팅하였다.

그래프 탐색 문제였으며, 모든 노드를 탐색해야 했기에 DFS를 활용하였다.

DFS 구현 자체가 어려운 문제가 아닌 미로 찾기처럼 상하좌우, 인접한 노드에 1이 있는지 판단해야 하는 문제였다고 생각한다.

다른 분들이 풀이한 코드들은 아직 확인해 보지 못했는데, DFS가 포함되면 거의 비슷할 것이라 생각한다.

정답 코드

// 접근 방법
// 모든 노드를 조사하며, 더 이상 조사되지 않을 때 지렁이 수++
// 모든 노드를 방문하는 것 -> DFS로 접근

// 해결해야 할 문제
// 어떻게 주어진 입력이 인접한 노드인지 알 수 있는가

#include <iostream>
#include <string.h>
#include <queue>

#define fastio std::ios_base::sync_with_stdio(false), std::cin.tie(NULL), std::cout.tie(NULL)

int main(void)
{
    // fast i/o;
    fastio;

    // First Input
    int T;
    int M, N, K;
    std::cin >> T;

    // For Search
    int x_dir[4] = {-1, 1, 0, 0}; // 상화 좌우 x축 방향
    int y_dir[4] = {0, 0, -1, 1}; // 상화 좌우 y축 방향

    int result;
    for (int test_case = 0; test_case < T; test_case++)
    {
        // For result,
        int result = 0;

        // Input
        std::cin >> M >> N >> K;

        // coord Input
        int x, y;
        int ground[N][M]; // N 세로, M 가로
        int visited[N][M]; // 방문 기록

        // Init array
        memset(ground, 0, sizeof(ground));
        memset(visited, 0, sizeof(visited));

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

        // 전체 좌표에 대해 방문되지 않고 배추가 심어져있는 부분이 있다면 그 지점부터 DFS 시작.
        for (int P = 0; P < N; P++)
        {
            for (int L = 0; L < M; L++)
            {
                if (visited[P][L] != 1 && ground[P][L] != 0)
                {
                    std::queue<std::pair<int, int>> q;
                    visited[P][L] = 1;
                    q.push(std::make_pair(P, L));
                    while (!q.empty())
                    {
                        int nx = q.front().first;
                        int ny = q.front().second;

                        q.pop();

                        for (int j = 0; j < 4; j++)
                        {
                            int nx_new = nx + x_dir[j];
                            int ny_new = ny + y_dir[j];

                            if ((0 <= nx_new && nx_new < N) && (0 <= ny_new && ny_new < M) && !visited[nx_new][ny_new] && ground[nx_new][ny_new] == 1)
                            {
                                visited[nx_new][ny_new] = 1;
                                q.push(std::make_pair(nx_new, ny_new));
                            }
                        }
                    }
                    result++; // whlie 종료 시 모든 노드를 탐색한 것이기에, 지렁이++;
                }
            }
        }
        // Print
        std::cout << result << "\n";
    }

    // last
    return 0;
}

GitHub

1012 : GitHub

📣
Baekjoon에서 맞은 코드만 업데이트합니다.
본 포스팅의 풀이 언어 및 개발 환경 : C++, VScode
풀이에 대한 오류나 궁금한 점은 Comments를 작성해주시면, 많은 도움이 됩니다.💡