#1012 유기농 배추 (C++)

링크 : www.acmicpc.net/problem/1012

1012번: 유기농 배추

밑줄에 주의

문제 풀이는 다음과 같다.

 

(1) 배열의 0,0부터 N,M까지 for문을 돌려서, 해당 위치가 1이고 방문해본적이 없다(false)면 DFS를 진행한다.

(2) 해당 위치는 방문한 표시를 해두고(true), 해당 위치의 상하좌우 위치를 탐색하여 

1번과 동일하게 1의 값을 가지고 방문해본적이 없으면 DFS를 진행한다. 

(3) 더이상 방문 가능한 공간이 없으면 DFS를 종료하고 벌레의 값을 +1 해준다. 

 

이렇게 해서 연계형식으로 상하좌우로 연결된 배추들은 모두 한번에 벌레 하나로 처리해주는 형식이다.

이런 문제는 원리는 어렵지 않지만, 주의해야할 점은

 

(1) 가로 세로의 입력과 for문 주의 (항상 엇갈리게 주고 받아야하는 포인트가 있다) 

(2) '배주의 위치가 0,0부터 가능'하다는 점이다. 

 

나는 1부터 세는 것을 좋아해서 항상 배열을 널널하게 잡는데, 

탐색마저도 1부터 가능하게 코드를 구현했다가 0이 포함된 위치를 탐색하지 못해서 값이 틀리게 나왔다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int t = 0, n = 0, m = 0, v = 0, mini = 0, arr[52][52], cnt = 0;
int h[4] = { 1,0,-1,0 }, w[4] = { 0,1,0,-1 }; // 상하좌우 배열
bool check[52][52];
vector<int> ans;

void dfs(int y, int x) {
    check[y][x] = true;
    for (int i = 0; i < 4; i++) {
        if (arr[y + h[i]][x + w[i]] == 1 && check[y + h[i]][x + w[i]] == false) {
            dfs(y + h[i], x + w[i]);
        }
        else continue;
    }
    return;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a = 0, b = 0;
    cin >> t;
    while (cnt < t) {
        cnt++;
        cin >> m >> n >> v; // 가로, 세로, 배추 갯수
        for (int i = 0; i < v; i++) {
            cin >> a >> b; // 가로, 세로
            arr[b][a]++;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 1 && check[i][j]==false) {
                    dfs(i, j);
                    mini++;
                }
            }
        }
        ans.push_back(mini);
        memset(arr, 0, sizeof(arr));
        memset(check, false, sizeof(check));
        mini = 0;
    }

    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] << "\n";

    return 0;
}

 

배열의 크기가 52*52로 되어있지만, 50*50으로 변경하고 관계되는 값은 변경해서 진행해도 무방하다.