백준 1012 (DFS)

1012번: 유기농 배추

과정

• 가로 세로로 지렁이가 움직일 수 있는 영역을 묶음으로 처리해야겠다고 생각했다.
• 처음에는 벡터에 배추가 심어진 좌표값을 하나씩 받고, 그것들의 평균치를 구해서 평균값에 들어오면 같은 묶음, 아니면 다른 묶음으로 처리하려고 했다. 하지만, 2*3마냥 진짜 무더기로 있는 경우 평균값을 어떻게 구해야할 지 몰랐고,
  
  추가적으로 문제를 잘못이해한 내용이 있다. 무조건 동서남북으로 5개까지만 이동 가능한 줄 알았는데, 계속 쭉 이동할 수 있었다.
• 결국 답을 찾아본 결과 DFS와 BFS로 푸는 거였다. 나는 전부터 BFS를 더 선호하는? 성향이었어서 DFS로 풀어보았다. 진짜 다 까먹었네..

코드

#include <iostream>

#include <vector>

using namespace std;

// 가로, 세로, 총 배추 개수

int M = 0;  // 가로

int N = 0;  // 세로

int K = 0;  // 총 배추 개수

int dx[] = { -1,1,0,0 };

int dy[] = { 0,0,-1,1 };

// 확인한 곳 : 0, // 확인하지 않은 곳 && 배추 있는 곳 : 1

void dfs(int x, int y, vector<vector<int>> &arr)

{

    // 확인 했으니까 일단 0으로 초기화

    arr[x][y] = 0;

    for (int i = 0; i < 4; i++)

    {

        int _x = x + dx[i];

        int _y = y + dy[i];

        // 지금 들어온 좌표기준 동서남북 중 1인 곳이 있으면 다시 dfs

        // 없으면 끝

        if (_x >= 0 && _x < M && _y >= 0 && _y < N && arr[_x][_y] == 1)

        {

            dfs(_x, _y, arr);

        }

    }

}

int main()

{

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    // 테스트 케이스 개수

    int T;

    cin >> T;

    for (int i = 0; i < T; i++)

    {

        cin >> M >> N >> K;

        // 배추밭

        // 주의 : 세로 가로로 설정

        vector<vector<int>> arr(N, vector<int>(M, 0));

        // 배추 심기

        for (int j = 0; j < K; j++)

        {

            int x, y;

            cin >> y >> x;

            arr[x][y] = 1;

        }

        // 지렁이 총 개수

        int count = 0;

        // 세로 먼저

        for (int n = 0; n < N; n++)

        {  

            // 가로에 대해

            for (int m = 0; m < M; m++)

            {

                if (arr[n][m] == 1)

                {

                    count++;

                    dfs(n, m, arr);

                }

            }

        }

        cout << count << "\n";

    }

}

 

주의할 점은, 일반적으로 사람이 그리는 X축, Y축 그래프좌표는 (X,Y)이지만, 벡터의 행과 열은 Y,X이므로

벡터를 처음 초기화할 때 Y,X가 되도록 구현해야한다. (이걸로 30분은 넘게 끙끙거렸다.)