[BOJ] #1012 유기농 배추

시간 제한	메모리 제한	정답 비율
1초	512MB	34.545%

 

1012번: 유기농 배추

 

문제

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.

예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.

(0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.)

해결

key point, DFS로 그래프가 몇 개 있는지 확인

1. 배추가 있는 곳을 1로 채우고
2. 왼쪽 상단부터 배추밭을 탐색하면서 배추가 있다면 dfs 함수에 간다.
3. 상하좌우 4방향에 배추가 있다면 방문한다.
4. 방문했다는 것을 표시하기 위하여 배추가 심어져 있지 않은 땅인것 처럼 0으로 표시해준다.
5. 함수에서 나오면 ans++해서 배추들이 모여있는 곳을 카운트한다. 

 

코드

메모리	시간
1996 KB	0 ms

#include <iostream>
#include <string.h>
using namespace std;
int t, n, m, k, arr[55][55], ans;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
void dfs(int x, int y) {
    arr[x][y] = 0;
    for (int k = 0; k < 4; k++) {
        int nx = x + dx[k], ny = y + dy[k];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m || !arr[nx][ny]) continue;
        dfs(nx, ny);
    }
 
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        for (int i = 0, a, b; i < k; i++) {
            scanf("%d%d", &a, &b);
            arr[a][b] = 1;
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j]) {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        printf("%d\n", ans);
        ans = 0;
        memset(arr, 0, sizeof(arr));
    }
    return 0;
}

 

후기

• 그렇게 틀리지 말자고 다짐했던 memset → string.h 에서 틀렸고
• or연산에서 | 하나만써서

총 컴파일에러 2번 틀리고 맞았다 으윽.. 풀기는 금방 풀어서 다행.

• 이전과 다르게 chk배열을 굳이 쓰지 않아도 풀리는 것을 캐치하고 arr배열 하나로 문제를 풀었다.