BOJ 1012 - 유기농 배추

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

1012번: 유기농 배추

 

DFS 를 이용해서 구분된 구역의 총 갯수를 구하는 문제였다.

 

이 문제를 풀면서 깨달았던 것은

1. 테스트 케이스가 여러개 주어지면 memset 으로 배열 초기화 작업을 해줘야 다음 테스트 케이스에서도 사용이 가능하다.

2. 인접 행렬에 대한 구분 구역의 갯수는 메인 함수에서 구하며, 구역 내에서의 찾고자하는 원소의 총합은 dfs 함수 내에서 구해야한다.

 

2번에 대한 부분은 BOJ 2667 문제를 풀면 이해가 간다.

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

(2667번 문제에 대한 답 : https://sdy-study.tistory.com/51)

 

- c++

#include <cstring>
#include <iostream>
#define MAX 51
 
using namespace std;
 
int T, M, N, K;  // T 는 테스트 케이스, M 은 가로 길이, N 은 세로 길이, K 는 배추위치 갯수
int checked[MAX][MAX];
int adj[MAX][MAX];
int dx[4] = {0, 0, -1, 1};  // 상하좌우
int dy[4] = {1, -1, 0, 0};
 
void dfs(int x, int y) {
    checked[x][y] = true;
 
    for (int k = 0; k < 4; k++) {
        int new_x = dx[k] + x;
        int new_y = dy[k] + y;
        if ((0 <= new_x && new_x < M) && (0 <= new_y && new_y < N)) {
            if (adj[new_x][new_y] == 1 && !checked[new_x][new_y]) {
                dfs(new_x, new_y);
            }
        }
    }
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
 
    cin >> T;
    for (int t = 0; t < T; t++) {
        memset(checked, 0, sizeof(checked));
        memset(adj, 0, sizeof(adj));
 
        cin >> M >> N >> K;
        for (int j = 0; j < K; j++) {
            int x, y;
            cin >> x >> y;
            adj[x][y] = 1;
        }
        int cnt = 0;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (adj[i][j] == 1 && !checked[i][j]) {
                    dfs(i, j);
                    cnt++;
                }
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

 

 

 

 

난이도가 너무 높지 않은 경우, DFS 나 BFS 의 문제를 풀다보면 코드의 구조가 꽤나 정형화 되어 있음을 알 수 있다.

DFS 의 경우 재귀함수로 풀어서 방문 여부 체크하고, dx[4], dy[4] 배열을 이용해서 상하좌우 이동 위치를 지정하고, 조건에 맞으면 DFS 를 수행하는 그런식으로 풀어가고,

BFS 의 경우, 재귀함수가 아닌 큐를 활용해서 dx[4], dy[4] 배열을 통해 좌표를 이동하여 조건에 맞는 대상을 찾아내고 

하는 그런 방식으로 진행되는게 일반적인것 같다.