1012 유기농 배추 문제 설명과 풀이 C++

안녕하세요 판타지코딩월드입니다!

 

오늘은 1012번 유기농 배추 문제 설명하고 풀이 하겠습니다.

 

배열을 활용하여 배추가 심어진 배추밭을 구현하고, dfs 함수로 인접한 배추를 탐색하는 문제입니다.

 

dfs의 개념을 잘 이해하셨다면 어렵지 않게 풀 수 있는 문제입니다.

 

그럼 문제 설명 시작합니다!

---

1. 문제 설명

 

유기농 배추를 재배하기 위해 배추흰지렁이를 풀어놓는다고 한다. 배추흰지렁이는 상하좌우 인접한 배추 근처를 돌아다닐 수 있기 때문에 상/하/좌/우 이동을 가정한 경우의 수를 계산해 주어야 하고, 대각선으로는 이동할 수 없다. 이렇게 상하좌우 인접한 배추들은 1개의 구역이라고 했을 때, 몇 개의 구역으로 나뉘어 있는지를 계산해서 몇 마리가 필요한지 출력해주면 된다.

 

아래의 예시 그림을 보자.

 

배추밭 예시

 

배추밭은 이 그림과 같이 배추가 심어져 있는 곳은 1, 그렇지 않은 곳은 0으로 표현한다. 이 경우 배추밭은 3개의 구역으로 나뉘게 된다.

 

2. 문제 풀이

 

배추밭이 몇 구역으로 나뉘는지를 확인하기 위해 DFS를 활용한다. 2차원 배열로 배추밭의 데이터를 저장하고, 2중 for문으로 1이 들어 있는 위치를 발견하면 dfs를 시작해서 인접한 구역은 방문 처리를 한다. 그렇게 몇 구역을 방문했는지 체크하면 필요한 배추흰지렁이 수를 구할 수 있다.

 

• DFS 코드 : 인접한 배추를 모두 탐색한다.

int dx[4] = {0, 1, 0, -1};  // x좌표 이동
int dy[4] = {1, 0, -1, 0};  // y좌표 이동

void dfs(int x, int y)
{
    for(int i=0; i<4; i++)
    {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || ny<0 || nx>=M || ny>=N)
            continue;
        if(map[ny][nx] && !check[ny][nx])
        {
            check[ny][nx] = true;
            dfs(nx, ny);
        }
    }
}

 

인접한 배추를 모두 확인하기 위해 배열 dx와 dy를 활용한다. 상하좌우 네 구역을 확인하면서 배추밭인 map에 1이 저장되어 있고, 방문 확인 배열인 check가 false일 경우 해당 부분에 다시 dfs를 수행한다. 이렇게 인접한 배우가 없을 때까지 탐색하고 나면 dfs 함수가 종료된다.

 

• 이중 for문 : 모든 배추밭을 순서대로 탐색하면서 배추가 심어져 있는 곳을 발견하면 dfs를 시작한다.

for(int j=0; j<N; j++)  // 세로 길이
{
    for(int r=0; r<M; r++)  // 가로 길이
    {
        if(map[j][r] && !check[j][r])  // 배추가 심어져 있고, 방문하지 않은 곳일 경우
        {
            check[j][r] = true;  // 방문 처리
            dfs(r, j);  // dfs 함수 시작
            cnt++;  // 구역 수 1개 증가
        }
    }
}

 

가로 길이가 M, 세로 길이가 N인 map의 모든 부분을 탐색하면서 배추가 심어져 있고, 방문한 적이 없는 위치를 발견하면 방문 처리를 하고 dfs를 수행하는 코드이다. 그리고 해당 부분에 dfs를 시작하면 인접한 모든 배추를 탐색하기 때문에 1개의 구역을 탐색하는 것이 된다. 그래서 마지막에 cnt 변수의 값을 1 더해준다.

 

3. 전체 코드

 

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

using namespace std;

int map[51][51];  // 배추밭
bool check[51][51];  // 방문한 배추 위치 체크
int cnt = 0;  //배추밭 구역 수
int dx[4] = {0, 1, 0, -1};  // x좌표 이동
int dy[4] = {1, 0, -1, 0};  // y좌표 이동
int M, N;  // X, Y 배추밭 크기

void dfs(int x, int y)
{
    for(int i=0; i<4; i++)
    {
        int nx = x+dx[i];
        int ny = y+dy[i];
        if(nx<0 || ny<0 || nx>=M || ny>=N)
            continue;
        if(map[ny][nx] && !check[ny][nx])
        {
            check[ny][nx] = true;
            dfs(nx, ny);
        }
    }
}

int main()
{
    int T;
    cin >> T;
    for(int i=0; i<T; i++)
    {
        int K;
        cin >> M >> N >> K;
        
        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 r=0; r<M; r++)
            {
                if(map[j][r] && !check[j][r])
                {
                    check[j][r] = true;
                    dfs(r, j);
                    cnt++;
                }
            }
        }
        cout << cnt << endl;
        cnt = 0;
        memset(check, 0, sizeof(check));
        memset(map, 0, sizeof(map));
    }
    
    return 0;
    
}

---

오늘은 DFS를 활용하여 배추밭에 있는 배추의 구역을 확인하고, 필요한 배추흰지렁이의 수를 출력하는 문제를 풀어보았습니다. 여기서 활용되는 cnt같은 변수와 check, map 같은 배열을 초기화하고 다음 테스트 케이스에 다시 활용해야 한다는 것을 숙지하고 문제 푸시면 오류 발생을 줄일 수 있습니다.

 

감사합니다!