[백준 1012번/C언어] 괄호 풀이

백준 1012번 문제를 풀어보았습니다. 

백준 1012번: https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

 

 

문제 내용은 아래와 같습니다. 

 

 

 

 

 제 블로그를 보시면 제가 비슷한 다른 문제들은 전역 변수 배열을 활용해서 해결해 왔다는 것을 알 수 있습니다. 하지만 이 문제 같은 경우에는 테스트 케이스가 한 번 실행에 하나가 아니기 때문에 전역변수를 사용하는 것의 이점이 크지 않습니다. (전역 변수를 사용하면 두 번째 테스트 케이스부터는 어차피 다시 0으로 초기화를 다 해야 하기 때문입니다.) 그래서 이 문제는 malloc을 활용하여 동적 할당을 통해 해결해 보았습니다. 

 배열을 통해 배추가 있는 위치를 표기해서, 전체 밭을 순회하면서 배추가 있는 위치를 마주하면 카운트를 늘리면서 인접한 배추가 있는 위치를 다 지워버려서 더 이상 인접한 배추에 대해서는 카운트가 되지 않도록 처리하는 방식을 사용했습니다.

 

 

 코드를 살펴보면, 크게 인접 배추의 위치를 다 지우는 removeAdj() 함수, 현재 수행 중인 테스트 케이스에 대한 밭 공간(배열)을 만드는 makeField() 함수, 몇 마리의 지렁이가 필요한지 세는 countWorm() 함수 그리고 메인 함수 이렇게 네 가지 함수로 나누어져 있습니다.

 main 함수를 먼저 보면, 우선 테스트 케이스의 갯수에 해당하는 T 값을 입력받고, T만큼 반복하는 반복문에서 가로길이에 해당하는 M, 세로 길이에 해당하는 N, 그리고 배추 개수에 해당하는 K를 입력받은 후 이를 이용하여 countWorm() 함수를 실행시킵니다. countWorm() 함수에서 M과 N의 순서를 바꿔서 넣은 이유는 가로길이가 M이고 세로 길이가 N이면 일반적으로 M이 y이고 N이 x인데, 순서가 반대로 주어져서 제 편의를 위해서 그렇게 사용했습니다. 그리고 제가 보통 2차원 배열이 나오면 헷갈리지 않기 위해서 변수 두 개를 x, y로 사용하는데, 여기서도 그렇게 했기 때문에 일반적인 수학적 상식 하에 2차원 배열을 진행시키기 위함이므로 혼동하시지 않게 주의해 주시기 바랍니다. 

 다음으로 countWorm() 함수에서는 우선 makeField() 함수를 이용해서 field를 만듭니다. makeField 함수에 대해서는 끝에 소개하도록 하겠습니다. 그리고 위치값을 받을 임시 변수 a와 b를 선언해주고, 입력받은 배추의 개수만큼 반복하며 위치값을 받아 field의 해당 위치에 배추가 있다는 표시로 1을 넣어줍니다. 뒤에 더 자세히 설명하겠지만 이미 makeField 함수에서 field 배열 전체를 0으로 초기화한 상태이기 때문에 0과 1로 배추가 있는 자리와 배추가 없는 자리가 완전히 구분되게 됩니다. 그 이후, 필요한 지렁이 개수를 세 줄 count 변수를 0으로 초기화하고, field 배열 전체를 순회하면서 배추가 있는 자리를 만나면 지렁이 개수를 증가시켜 준 후 주변 위치의 배추 표시를 없애주기 위해 removeAdj() 함수를 호출해 줍니다. 마지막으로 field 배열의 메모리를 해제해 준 후 세어둔 지렁이 개수를 리턴해주면 countWorm() 함수가 마무리되게 됩니다. 

 removeAdj() 함수는 앞서 간단히 언급한 것처럼 이미 세어진 배추 위치에 인접한 모든 배추의 위치를 배추가 없다는 뜻인 0으로 바꿔주어야 합니다. 그래서 해당 위치의 바로 위칸(x - 1, y), 왼쪽칸(x, y-1), 아래칸(x+1, y), 오른쪽칸(x, y+1) 이렇게 네 칸 중 배추가 있는 칸이 있다면 해당 칸을 0으로 만들어 준 후 재귀를 통해 그 칸의 인접 칸 배추까지 모두 제거해줍니다. 

 makeField() 함수는 메모리가 할당된 투포인터 변수를 리턴하는 함수로, 세로의 길이(X)와 가로의 길이(Y)를 입력받아 그 크기만큼의 이차원 배열을 만들게 됩니다. 이 과정에서, 메모리 할당이 정상적으로 동작하지 않는다면 NULL을 리턴합니다. 그리고 마지막으로 모든 요소들을 0으로 초기화해준 후, 초기화된 배열을 리턴합니다. 0으로 모두 초기화하지 않으면 쓰레기값이 들어가고, 그러면 배추가 있는 위치에 1을 저장한다고 해도 다른 값이 랜덤 하여 배추가 있는 자리와 없는 자리의 구분이 어려워집니다. 따라서 배열에 메모리 할당을 해주고 나서, 모든 배열을 추후 직접 초기화해 주는 게 아니라면 값들을 초기화해 주는 과정이 반드시 필요합니다. 

#include <stdio.h>
#include <stdlib.h>

void removeAdj(int x, int y, int X, int Y, char ***field) {
    if (x > 0 && (*field)[x-1][y]) {
        (*field)[x-1][y] = 0;
        removeAdj(x-1, y, X, Y, field);
    }
    if (y > 0 && (*field)[x][y-1]) {
        (*field)[x][y-1] = 0;
        removeAdj(x, y-1, X, Y, field);
    }
    if ((x + 1) < X && (*field)[x+1][y]) {
        (*field)[x+1][y] = 0;
        removeAdj(x+1, y, X, Y, field);
    }
    if ((y + 1) < Y && (*field)[x][y+1]) {
        (*field)[x][y+1] = 0;
        removeAdj(x, y+1, X, Y, field);
    }
}

char **makeField(int X, int Y) {
    char **field = (char **)malloc(sizeof(char *) * X);
    if (field == NULL) return NULL;
    
    for (int i = 0; i < X; i++) {
        field[i] = (char *)malloc(sizeof(char) * Y);
        if (field[i] == NULL) {
            for (int j = 0; j < i; j++) free(field[j]);
            return NULL;
        }
    }
    
    for (int i = 0; i < X; i++) {
        for (int j = 0; j < Y; j++) {
            field[i][j] = 0;
        }
    }
    
    return field;
}

int countWorm(int X, int Y, int loc) {
    char **field = makeField(X, Y);
    if (field == NULL) return (-1);
    
    int a, b;
    for (int i = 0; i < loc; i++) {
        scanf("%d %d", &a, &b);
        field[b][a] = 1;
    }
    
    int count = 0;
    for (int x = 0; x < X; x++) {
        for (int y = 0; y < Y; y++) {
            if (field[x][y]) {
                removeAdj(x, y, X, Y, &field);
                count++;
            }
        }
    }
    
    for (int i = 0; i < X; i++) free(field[i]);
    free(field);
    return count;
}

int main() {
    int T;
    scanf("%d", &T);
    
    for (int i = 0; i < T; i++) {
        int M, N, K;
        scanf("%d%d%d", &M, &N, &K);
        printf("%d\n", countWorm(N, M, K));
    }
}