유기농 배추

작성일 | In

[백준] 1012번 - 유기농 배추

문제 링크

그래프 탐색을 이용하여 인접한 구역의 개수를 구하는 문제이다.
2차원 배열을 순서대로 탐색하며 이전에 방문하지 않았고, 유기농 배추가 심어져 있는 칸에 도달할 때 그 좌표에서 dfs 혹은 bfs를 수행한다면 구역 한 개를 구할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

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

int m,n;

void bfs(int sy, int sx, vector<vector<bool>>& field, vector<vector<bool>>& visited) {
    queue<pair<int, int>> que;
    visited[sy][sx] = true;
    que.push({sy, sx});

    while(!que.empty()) {
        int y = que.front().first;
        int x = que.front().second;
        que.pop();

        for(int i=0; i<4; ++i) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if(ny < 0 || ny >= n || nx < 0 || nx >= m)
                continue;
            if(!field[ny][nx])
                continue;
            if(visited[ny][nx])
                continue;
            
            visited[ny][nx] = true;
            que.push({ny, nx});
        }
    }
}

int main(void) {
    int t;
    scanf("%d", &t);

    while(t--) {
        int k;
        scanf(" %d %d %d", &m, &n, &k);
    
        vector<vector<bool>> field(n);
        for(int i=0; i<n; ++i)
            field[i].resize(m, false);

        vector<vector<bool>> visited(n);
        for(int i=0; i<n; ++i)
            visited[i].resize(m, false);

        for(int i=0; i<k; ++i) {
            int x, y;
            scanf("%d %d", &x, &y);
            field[y][x] = true;
        }

        int ans=0;
        for(int i=0; i<n; ++i) {
            for(int j=0; j<m; ++j) {
                if(!visited[i][j] && field[i][j]) {
                    bfs(i, j, field, visited);
                    ++ans;
                }
            }
        }

        printf("%d\n", ans);
    }
}
0%