[c++ | 백준] 1012번 유기농 배추

c++ 문제 풀이

 

 

 

 

 

---

 

 

[백준 1012번 유기농 배추 문제]

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

 

 

 

 

---

 

 

 

전체 풀이 코드

#include <iostream>
using namespace std;

int testcase, m, n, num, x, y;
int board[51][51];
bool visited[51][51];

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

void DFS(int y, int x)
{
    visited[y][x] = true;
    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (board[ny][nx] == 1 && visited[ny][nx] == false)
            DFS(ny, nx);
    }
    return;
}

int main(void)
{
    cin >> testcase;
    while (testcase--)
    {
        fill_n(board[0], 51 * 51, 0);
        fill_n(visited[0], 51 * 51, 0);

        int cnt = 0;
        cin >> m >> n >> num;
        for (int i = 0; i < num; ++i)
        {
            cin >> x >> y;
            board[y][x] = 1;
        }

        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (board[i][j] == 1 && visited[i][j] == false)
                {
                    DFS(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';

    }

    return 0;
}

 

 

 

풀이 설명

 

1. 전역 변수

// 테스트케이스 개수, 배추밭의 가로 길이 m, 세로 길이 n, 배추 개수 num, 배추의 위치 x, y
int testcase, m, n, num, x, y;

int board[51][51]; // 배추밭을 나타내는 배열
bool visited[51][51]; // 배추밭에 있는 배추를 방문했는지 나타내는 배열

// 상 하 좌 우를 검사하기 위한 배열
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };

 

 

이제 부터 DFS로 문제를 풀어볼겁니다. main 함수 부터 설명드리도록 하겠습니다.

 

 

2. main 함수

int main(void)
{
    cin >> testcase;
    while (testcase--)
    {
        fill_n(board[0], 51 * 51, 0);
        fill_n(visited[0], 51 * 51, 0);

        int cnt = 0;
        cin >> m >> n >> num;
        for (int i = 0; i < num; ++i)
        {
            cin >> x >> y;
            board[y][x] = 1;
        }

        ...

처음 testcase의 개수를 입력받은 후 while문을 testcase만큼 돌아줄겁니다. 그 후에 board 배열과 visited 배열을 초기화 해줍니다.

testcase마다 벌레의 개수를 출력해줘야하기 때문에 변수 cnt를 만들어서 벌레의 개수를 세줄 겁니다.

다음으로 m, n, num을 입력받은 후 배추의 개수만큼 for문을 돌면서 board배열 y,x 좌표에 배추가 있음을 1로 표시하여줍니다.

 

 

		...
	
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < m; ++j)
			{
				if (board[i][j] == 1 && visited[i][j] == false)
				{
					DFS(i, j);
                    			cnt++;
				}
			}
		}
		cout << cnt << '\n';
	}
    return 0;
}

다음으로 배추밭의 크기만큼 이중for문을 돌면서 현재 좌표에 배추가 있고 한 번도 방문하지 않은 좌표인지 검사하여 맞다면 DFS함수를 실행해준뒤 cnt를 1 올려줍니다.

 

그 이유를 설명드리겠습니다.

이렇게 생긴 배추밭이 있다고 생각해봅시다.

 

DFS는 재귀함수로 이루어져 있기 때문에 주변에 붙어있는 밭들을 모두 방문할 수 있습니다.

 

이때 방문한 밭은 visited를 통해 방문했음을 표시할 것이기 때문에 다른 곳을 검색할 때 문제가 발생하지 않게 됩니다.

 

 

따라서 이 배추밭에 필요한 벌레의 개수는 5마리가 되는 것 입니다.

이제 DFS 함수를 설명드리도록 하겠습니다.

 

 

3. DFS 함수

void DFS(int y, int x)
{
    visited[y][x] = true;
    for (int i = 0; i < 4; ++i)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
        
        ...

DFS 함수는 배추의 y(행)과 x(열) 좌표를 매개변수로 받습니다.

 

먼저 현재 좌표의 배추를 방문했음을 visited를 통해 표시한뒤 현재 배추의 상하좌우를 확인해줄겁니다.

dy 배열과 dx 배열을 이용하여 검사할 밭의 좌표를 ny, nx로 구합니다. (상하좌우)

 

 

    ...
    
    if (ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
        if (board[ny][nx] == 1 && visited[ny][nx] == false)
            DFS(ny, nx);
    }
    return;
}

위에서 구한 ny, nx좌표가 배열의 범위를 넘어갔는지 체크하고 넘어갔다면 continue를 해줍니다.

 

배열의 범위를 넘어가지 않은 좌표라면 그 좌표의 배추가 있는지, 방문 하지 않은 좌표인지 if문으로 확인한 뒤 맞다면 DFS 함수를 실행해 ny, nx좌표를 넘겨줍니다.

 

이렇게 재귀 함수를 실행하여 주변의 배추가있으면서 방문하지 않은 곳들을 모두 방문하게 됩니다.

 

 

---

 

이렇게 백준 1012번 문제를 DFS로 풀이해보았습니다.

궁금한점 있으시면 댓글 남겨주세요!