[Algorithm] BOJ : 유기농 배추

안녕하세요, iOS 개발하는 루피입니다.

 

이번 글에서는 DFS 문제인 백준 1012 문제를 공부 해보려합니다. 이 문제의 목표는 2차원 배열로 표현된 배추밭에서 상하좌우로 연결된 배추들을 하나의 군집으로 보고, 그 군집의 개수를 세는 것입니다. 이 과정에서 DFS를 사용해 여러 방향으로 연결된 배추들을 한 번에 탐색할 수 있을거 같습니다.

전체적인 플로우는 이렇게 될 거 같은데요..

1. 배추 좌표를 입력받고 배열에 기록.
2. 배추밭을 순회하며 아직 방문하지 않은 배추를 찾는다.
3. DFS를 통해 연결된 배추들을 하나의 군집으로 보고 탐색을 완료.
4. 군집의 수를 카운트한 후 출력합니다.

변수 설정

int board[51][51];  // 배추밭을 표현하는 배열 (최대 50x50 크기)
int visited[51][51];  // 방문 여부를 체크하는 배열
int dy[4] = { 0, 1, 0, -1 };  // y축 이동을 위한 배열 (오른쪽, 아래, 왼쪽, 위)
int dx[4] = { 1, 0, -1, 0 };  // x축 이동을 위한 배열

배열 dy와 dx는 상하좌우로 움직이기 위해 사용됩니다. 왜 dy[1], dx[1]이 아래로 가는지 헷갈릴 수 있는데, 2차원 배열에서 y가 1 증가하면 아래로 한 칸 이동한다는 점을 기억하면 쉽게 이해할 수 있어요!!!

DFS 함수

DFS는 재귀적으로 상하좌우를 탐색하면서 연결된 배추들을 한 번에 처리해줍니다.

void dfs(int y, int x) {
    for (int i = 0; i < 4; i++) {  // 상하좌우 네 방향을 확인
        int newY = y + dy[i];  // 새로운 y좌표
        int newX = x + dx[i];  // 새로운 x좌표

        // 방문 안 했고, 배추가 있다면
        if (visited[newY][newX] == 0 && board[newY][newX] == 1) {
            visited[newY][newX] = 1;  // 방문 처리
            dfs(newY, newX);  // 재귀적으로 연결된 배추 탐색
        }
    }
}

핵심은 DFS가 상하좌우 네 방향을 모두 탐색하는 구조입니다. 만약 방문하지 않았고, 해당 좌표에 배추가 있다면 그 방향으로 재귀 호출을 통해 계속 탐색합니다.

메인 함수

이제 전체 흐름을 관리하는 메인 함수입니다. board와 visited 배열을 초기화한 후, 각 배추 좌표를 입력받고 배추 군집을 찾습니다.

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int testCase; cin >> testCase;

    while (testCase--) {
        int cnt = 0;  // 배추 군집의 수
        int M, N, K; cin >> M >> N >> K;  // 배추밭의 가로 M, 세로 N, 배추의 수 K 입력

        memset(board, 0, sizeof(board));  // 배추밭 배열 초기화
        memset(visited, 0, sizeof(visited));  // 방문 배열 초기화

        for (int i = 0; i < K; i++) {
            int x, y; 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] == 0) {  // 배추가 있고, 아직 방문하지 않은 경우
                    visited[i][j] = 1;  // 방문 처리
                    dfs(i, j);  // 연결된 배추를 탐색
                    cnt++;  // 군집을 찾았으므로 카운트 증가
                }
            }
        }
        cout << cnt << '\\n';  // 각 테스트 케이스별로 군집의 수 출력
    }
}

전체 코드

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int board[51][51];  // 배추밭을 표현하는 배열 (최대 50x50 크기)
int visited[51][51];  // 방문 여부를 체크하는 배열
int dy[4] = { 0, 1, 0, -1 };  // y축 이동을 위한 배열 (오른쪽, 아래, 왼쪽, 위)
int dx[4] = { 1, 0, -1, 0 };  // x축 이동을 위한 배열

void dfs(int y, int x) {
    for (int i = 0; i < 4; i++) {  // 상하좌우 네 방향을 확인
        int newY = y + dy[i];  // 새로운 y좌표
        int newX = x + dx[i];  // 새로운 x좌표
        if (visited[newY][newX] == 0 && board[newY][newX] == 1) {  // 방문 안 했고, 배추가 있다면
            visited[newY][newX] = 1;  // 방문 처리
            dfs(newY, newX);  // 재귀적으로 연결된 배추 탐색
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int testCase; cin >> testCase;
    
    while (testCase--) {
        int cnt = 0;  // 배추 군집의 수
        int M, N, K; cin >> M >> N >> K;  // 배추밭의 가로 M, 세로 N, 배추의 수 K 입력
        
        memset(board, 0, sizeof(board));  // 배추밭 배열 초기화
        memset(visited, 0, sizeof(visited));  // 방문 배열 초기화
        
        for (int i = 0; i < K; i++) {
            int x, y; 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] == 0) {  // 배추가 있고, 아직 방문하지 않은 경우
                    visited[i][j] = 1;  // 방문 처리
                    dfs(i, j);  // 연결된 배추를 탐색
                    cnt++;  // 군집을 찾았으므로 카운트 증가
                }
            }
        }
        cout << cnt << '\n';  // 각 테스트 케이스별로 군집의 수 출력
    }
}