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

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

1012번: 유기농 배추

 

문제 요약

 

지렁이는 인접한 다른 배추로 이동할 수 있다. (한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접한 것)

배추가 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리가 필요한지 알 수 있다. 

 

 

범위

 

배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50), 세로길이 N(1 ≤ N ≤ 50) 

배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)

배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)

(배추의 위치가 같은 경우는 없다)

 

 

 

---

 

 

서로 인접해있는 배추들이 몇 군데에 퍼져있는지를 카운트 하면 필요한 최소 배추흰지렁이의 개수를 알 수 있다.

상하좌우로 이동할 수 있는 위치로 이동하면서 방문체크를 해준다. 더이상 방문할 수 있는 배추가 없다면 빠져나와서 다른 방문하지 않은 배추를 찾는다. 새로운 배추 그룹을 발견하면 카운팅을 해준다.

 

#include <iostream>
using namespace std;
int t, n, m, k, x, y, cnt = 0;
bool visited[51][51];
int a[51][51], dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void dfs(int nx, int ny){
    visited[nx][ny] = true;
    for(int i=0; i<4; i++){
        int dx = nx + dir[i][0];
        int dy = ny + dir[i][1];
        if(dx < 0 || dy < 0 || dx >= n || dy >= m) continue;
        if(a[dx][dy] == 0) continue;
        if(visited[dx][dy]) continue;
        dfs(dx, dy);
    }
}

void solution(){
    cnt = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(!visited[i][j] && a[i][j] == 1){
                cnt++;
                dfs(i, j);
            }
        }
    }
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--){
        cin >> m >> n >> k;
        for(int i=0; i<n; i++) for (int j=0; j<m; j++) a[i][j] = 0; //초기화
        for(int i=0; i<n; i++) for (int j=0; j<m; j++) visited[i][j] = false; //초기화
        for(int i=0; i<k; i++){
            cin >> y >> x;
            a[x][y] = 1;
        }
        solution();
    }
    return 0;
}

 

 

 

x와 y가 헷갈려서 당황스러웠다. 가로길이가 m이고 세로길이가 n이므로 x좌표는 m을 넘어서면 안되고 y좌표는 n을 넘어서면 안된다.

2차원 배열 a[i][j]에서 i가 행(row) → 세로(y좌표), j가 열(column) → 가로(x좌표)

그리고 여러 번의 테스트 케이스를 입력받기 때문에 초기화해주는 것은 필수다. 

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!