[C/C++] 백준 1012, DFS

1012번: 유기농 배추 (acmicpc.net)

1012번: 유기농 배추

strategy

1. connected component를 찾는 문제입니다

(1) cc_cnt라는 변수를 생성하여 connecte component를 탐색합니다

2. map[1000][1000]배열에 배추의 위치를 표시합니다

(1) 배추가 있는 곳=1

(2) 배추가 없는 곳=0

3. 배추A와 인접한 배추는 해당 배추A의 상, 하, 좌, 우에 위치한 것입니다

(1) 상, 하, 좌, 우는 x좌표 또는 y좌표에 1을 더하거나 뺀 위치입니다

(2) (1)의 개념을 이용해 인접한 배추를 효율적으로 찾으려면 배열과 반복문을 이용합니다

(3) 사용할 배열(dx, dy) : dx[4]={0, 0, -1, 1} & dy[4]={-1, 1, 0, 0}

(4) 반복문 for(int a=0;a<4;a++)를 사용하여 map[i+dx[a]][j+dy[a]]를 탐색하면 상, 하, 좌, 우를 탐색할 수 있습니다

4. 밭을 M*N개의 칸으로 생각하여, 각각을 정점으로 합니다.

(1) 배추가 있는 정점 u=k+j*w에 인접한 배추가 있는 정점 v=v = k + dx[a] + w * (j + dy[a])를 edge에 표시합니다

(2) edge에 표시한 것을 기반으로 connected component의 갯수를 도출합니다

 

#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> edge[2500];
int visit[2500];
short map[51][51];
int dx[4] = { 0,0,-1,1 };   //상하좌우를 탐색할 때 사용
int dy[4] = { -1,1,0,0 };   //상하좌우를 탐색할 때 사용

void dfs(int v) {
    if (visit[v] == 1)
        return;
    visit[v] = 1;
    for (int i = 0; i < edge[v].size(); i++)
        dfs(edge[v][i]);
}

int main() {

    int tc;
    int w, h, n;
    int x, y;
    int j, k;
    int u, v;
    int cc_cnt;

    scanf("%d", &tc);
    while (tc > 0) {
        for (j = 0; j < 2500; j++)
            edge[j].clear();
        for (j = 0; j < 2500; j++)
            visit[j] = 0;
        for (j = 0; j < 51; j++)
            for (int k = 0; k < 51; k++)
                map[j][k] = 0;
        cc_cnt = 0;
        scanf("%d %d %d", &w, &h, &n);
        for (j = 0; j < n; j++) {
            scanf("%d %d", &x, &y);
            map[x][y] = 1;
        }

        for (j = 0; j < h; j++) {
            for (k = 0; k < w; k++) {
                if (map[k][j] == 0)
                    continue;

                u = k + j * w;
                int flag = 0;

                for (int a = 0; a < 4; a++) {
                    if (map[k + dx[a]][j + dy[a]] == 0)
                        continue;
                    v = k + dx[a] + w * (j + dy[a]);
                    edge[u].push_back(v);
                    flag = 1;
                }
                if (flag == 0)
                    cc_cnt++;
            }
        }

        for (j = 0; j < w * h; j++) {
            if (edge[j].size() == 0)
                continue;
            sort(edge[j].begin(), edge[j].end());
        }

        for (j = 0; j < w * h; j++) {
            if (edge[j].size() == 0)
                continue;

            if (visit[j] == 0) {
                dfs(j);
                cc_cnt++;
            }
        }
        tc--;
        printf("%d\n", cc_cnt);
    }
}