[백준/C++] 1012번 : 유기농 배추

• 문제

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

• 코드

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

using namespace std;

int arr[51][51];
bool visited[51][51];
int m, n, k;

void dfs(int a, int b) {
    // 방향 벡터 정의 (상하좌우)
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    visited[a][b] = true;
    
    for (int i = 0; i < 4; ++i) {
        int nx = a + dx[i];
        int ny = b + dy[i];
        
        if (nx >= 0 && nx < m && ny >= 0 && ny < n && arr[nx][ny] == 1 && !visited[nx][ny]) {
            dfs(nx, ny);
        }
    }
}

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));
        
        cin >> m >> n >> k;
        
        for (int i = 0; i < k; ++i) {
            int x, y;
            cin >> x >> y;
            arr[x][y] = 1;
        }
        
        int worm_count = 0;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (arr[i][j] == 1 && !visited[i][j]) {
                    dfs(i, j);
                    worm_count++;
                }
            }
        }
        
        cout << worm_count << endl;
    }
    
    return 0;
}

• 알고리즘 분류 : DFS
• 문제 해설

2차원 배열 형태로 DFS, BFS 가 나오는 경우 배열의 양 끝을 예외처리하고 상하좌우를 탐색하는 배열을 미리 만들어놓아야 효율적으로 코드를 작성할 수 있었다. 또한 visited를 dfs 진행할 때마다 초기화 해야한다고 잘못 생각하고 있었는데 인접해 있는 한 그래프는 어차피 똑같은 카운트 값이 나오기 때문에 그럴 필요 없다는 것을 기억해야겠다.