[Unsolved][C++] 백준 1012 유기농 배추

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

1012번: 유기농 배추

 

1. 서론

 

DFS 문제인데... 어렵다? 그냥 푸는 방법을 모르는 듯

 

2. 문제 풀이

 

2차원 배열이 주어진다. 2차원 배열을 밭이라고 생각하고 배열의 값이 0인 경우에는 배추가 심어져 있지 않은 땅, 1인 경우에는 배추가 심어져 있는 땅을 의미한다. 배추를 해충으로부터 보호하기 위해 배추 흰 지렁이를 풀어야 하는데 이 지렁이를 최소로 풀었을 때 몇 마리인가를 구하는 문제이다. 배추 흰 지렁이는 배추가 있는 곳에서 상하좌우로 이동 가능하다. 

 

나는 사실 예시마저 이해하지 못했다. 왜냐하면 문제를 잘못 이해했기 때문에^^

나는 지정된 위치에서 딱 한 번만 상하좌우로 움직일 수 있다고 생각했는데 그게 아니었다. 

상하좌우로는 계속 움직일 수 있는데 상하좌우로 이동해도 닿을 수 없는 곳에 있으면 그때 다른 지렁이를 쓰는 것이었다. 

위와 같은 방법으로 최소 지렁이 수를 count 하는 것이다. 그야말로 미로 찾기 같은 문제.

 

출처: https://bitwise.tistory.com/70

백준 1012번: 유기농 배추(DFS)

그 사실들을 이 블로그를 보고 깨달았다.

결국엔 배추가 있는 곳에서 상하좌우로 이동하면서 다른 배추를 찾다가 상하좌우에 배추가 없는 상황이 오면 count를 한 번 하고 이를 2차원 배열의 끝까지 반복하는 것이다.

 

3. 코드 설명

 

#include <vector>
#include <cstring>
#include <iostream>

using namespace std;

int n, x, y;
int dx[] = {0, -1, 1, 0}, dy[] = {-1, 0, 0, 1};
int board[51][51] = {0,}, visited[51][51] = {0,};

void dfs(int a, int b)
{
    visited[a][b] = true;

    for (int i = 0; i < 4; i++)
    {
        int ax = a + dx[i];
        int ay = b + dy[i];

        if (ax < 0 || ay < 0 || ax >= x || ay >= y)
            continue;
        
        if (!board[ax][ay] || visited[ax][ay])
            continue;

        dfs(ax, ay);
    }
}
int main()
{
    int t, i, j, a, b, k;

    cin >> t;

    for (k = 0; k < t; k++)
    {
        cin >> x >> y >> n;

        for (i = 0; i < n; i++)
        {
            cin >> a >> b;
            board[a][b] = 1;
        } 

        int cnt = 0;
        for (i = 0; i < x; i++)
        {
            for (j = 0; j < y; j++)
            {
                if (board[i][j] == 1 && !visited[i][j])
                {
                    cnt++;
                    dfs(i, j);
                }

            }
        }
        cout << cnt << endl;

        memset(board, 0, sizeof(board));
        memset(visited, 0, sizeof(visited));
    }
}

 

의외로 코드가 간결해서 놀랐다.

문제에서 주어진 값들을 입력받고 지렁이들을 count 하기 위해 2차원 배열을 반복문으로 탐색한다.

배추가 있고 방문했다고 체크하지 않은 경우에 지렁이를 한 번 count 하고 dfs 함수 안으로 들어가 탐색을 시작한다.

 

dfs 함수

매개변수로 넘어온 좌표를 방문했다고 표시한 후 해당 좌표의 상하좌우에 배추가 있는지 확인한다. 

이때 범위를 넘어가지 않게 해야 하고, 배추가 있는지, 방문한 적은 없는지 같이 확인해준다.

만약 범위가 넘어가거나 배추가 없거나 방문한 적이 있다면 함수를 빠져나오게 된다.

 

그리고 문제에서 테스트를 여러 번 할 수 있게 input을 받기 때문에 board, visited를 재활용하기 위해서 초기화해준다.

 

꽤 여러 블로그를 찾았는데 가장 이해가 쏙 되면서 간결한 코드였다... 😇

ASAP 다시 풀 것...