[백준 2667번/C언어] 단지번호붙이기 풀이

백준 2667번 문제를 linked list와 재귀함수를 사용하여 풀어보았습니다.

 

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

2667번: 단지번호붙이기

 

 

 

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

 

 

 

 이 문제는 어렵다기보다는 이것저것 고려할 게 많아서 좀 번거로운 문제에 가깝다고 느꼈습니다. 2차원 배열을 만들어서 입력을 받아야 하고, 그 안에서 단지의 개수를 셈과 동시에 한 단지 내의 몇 개의 가구가 포함되는지도 세어야 하고, 또 결과적으로는 몇 개의 가구가 각각의 단지에 포함되었는지 오름차순으로 정렬하여 출력해야 하는 문제입니다. 

 저는 단지의 수와 각 단지 내 가구의 수를 세기 위해서는 recursive function을 활용하여 구현해줬고, 단지 별 가구의 수를 오름차순으로 저장해 두기 위해서는 linked list를 사용했습니다. linked list를 사용한 이유는, linked list의 특성상 정렬이 용이하고, 배열 크기를 따로 설정하지 않아도 되기 때문에 해당 문제의 특성과 그 장점이 잘 맞다고 판단해서입니다. 

 

 

 

 

 

 코드는 총 하나의 구조체와 네 개의 함수를 사용했습니다. 구조체는 가구 수 저장을 위한 연결리스트 생성에 사용했고, 첫 번째 함수인 makeMap() 함수는 2차원 배열을 크기에 맞게 생성하고 지도를 입력받는 데에 사용했습니다. 두 번째 함수인 makeElem() 함수는 연결리스트 내 각각의 노드를 보다 간편하게 생성하기 위해서 사용했으며, 세 번째 함수인 findHouse() 함수는 하나의 단지 내 가구의 수를 세면서 이미 방문한 가구를 삭제해주기 위해서 사용했습니다. 마지막으로 main 함수 내에서는 지도 배열을 순회하면서 가구가 있으면 단지 수를 세주고, 해당 단지의 가구의 수를 세기 위해 findHouse()를 사용하여 필요한 정보를 취합한 후, 만들어진 linked list를 순회하며 집의 수를 오름차순으로 출력했습니다. 

 

코드를 조금 더 자세히 보겠습니다.  main 함수르 보면, 우선 지도의 크기인 N을 입력받는 것으로 시작합니다. 그 이후 makeMap() 함수로 map 배열을 생성하여 지도를 입력받습니다

 makeMap() 함수를 좀 더 자세히 살펴보겠습니다. 우선 map 배열을 char type으로 선언했습니다. 우리가 궁극적으로 얻는 정보는 0 또는 1이라는 숫자이지만, 입력되는 형식도 '0'이나 '1'이라는 문자이기 때문에 char로 선언해 주면 따로 숫자로 변환해 줄 필요가 없고, 이후 처리하는 데도 딱히 불편함이 없기 때문에 편의상 char type으로 선언해 주었습니다. 또한 정보를 입력받을 때도, 줄 단위로 문자열로 입력받을 수 있기 때문에 더욱 용이합니다. 부가적으로 작은 차이이기는 하나, 메모리도 char type이 더 작기 때문에 공간 효율 면에서도 이득입니다. 이렇게 만들어진 map 배열에 N개의 줄을 다시 하나씩 생성해 주며 입력받습니다. 앞서 언급했듯 문자열 단위로 한 줄씩 입력받을 수 있습니다. 마지막으로 이렇게 입력받은 map 배열을 리턴해주어 main 함수 내 map 배열에 할당해 주면 됩니다. 

 

 이제 이렇게 만들어진 map 배열을 순회하면서 단지를 세주면 됩니다. 우선 단지 내 가구수를 저장해 줄 linked list를 먼저 생성해 줍니다. head 노드를 만들어주고, 그 뒤에 이어 붙이면 됩니다. head 노드를 만들어주기 위해서 makeElem() 함수를 사용해 줬습니다.

 makeElem() 함수를 좀 더 자세히 살펴보겠습니다. 우선 elem 포인터 변수를 생성해 주고, 메모리를 할당해 줍니다. 그리고는 인자로 입력받은 num을 구조체 내 num 정보에 저장해 주고, 입력받은 next를 구조체 내 next 정보에 저장해 줍니다. 이렇게 저장해 주면, num은 해당 단지 내 가구수가 될 것이고, next로 다음 단지 정보를 담은 노드가 그 뒤에 이어지게 됩니다.  

 

head 변수에 linked list의 첫 노드를 일단 가구수를 0으로 설정해서 담아주고, 단지 수 정보를 담을 count 변수를 0으로 초기화해 준 후 이중 loop로 map 배열을 순회하기 시작합니다. 만약, map 배열 내 현재 위치(x, y)에 '0'이 저장되어 있다면, 해당 위치에는 집이 없다는 의미이므로 다음으로 넘겨줍니다. 아니라면 해당 위치에 집이 있다는 뜻이므로, 해당 단지 내 가구 수를 카운트해주어야 합니다. 우선 해당 위치는 이미 순회한 셈이므로, 다시 세어지지 않도록 집이 없다는 의미의 '0'으로 그 값을 바꾸어주고 단지의 수를 하나 증가시켜 줍니다. 그리고 num 변수에 findHouse() 함수로 카운트 한 해당 단지 내 가구수를 저장해 줍니다.

 여기서 findHouse() 함수를 자세히 살펴보면, 앞서 언급했듯, 현재 위치의 집을 포함한 단지 내 가구수를 세주는 함수입니다. 우선 이 함수에 들어왔다는 것 자체가 현재 위치의 집이 단지에 포함된다는 뜻이므로, 카운트값은 1부터 시작합니다. 이후 현재 집 위치의 위아래 그리고 양 옆에 집이 있는지 확인해 주고, 만약 있다면 그 재귀를 통해 그 집부터 다시 카운트한 가구수 값을 현재 카운트값에 더해줍니다. 마지막으로 카운트된 값을 리턴해주면 단지 내 가구수를 셀 수 있게 됩니다. 

 

 이렇게 가구수까지 알았다면 이제 이를 linked list 내에 오름차순으로 정렬해서 저장해주어야 합니다. 만약 head 노드의 가구수 정보가 0이라면 이는 아직 저장된 노드가 없다는 뜻이므로 head에 현재 단지 정보 노드를 저장해 줍니다. 만약 현재 단지 내 가구수가 head 노드에 저장된 가구수보다 적다면, 이 노드가 첫번째로 와야하므로 head를 현재 단지 정보 노드로 대체해주고, 현재 노드의 다음 노드로 기존 head 노드를 저장해줍니다.

 만약 둘 다 아니라면 이제 적절한 위치를 찾아 끼워 넣어야 합니다. curr 변수를 정의해 주고 head부터 순회합니다. 만약 curr 노드의 다음 노드의 가구수가 현재 단지 정보의 가구수보다 크다면 현재 단지 정보 노드는 그보다 앞에 들어가야 할 것이기 때문에 해당 위치에서 순회를 멈춰주고, curr 노드의 다음 노드가 현재 단지 정보 노드가 되고, 그다음 노드를 현재 curr->next 노드로 넣어주면 정렬된 연결리스트가 됩니다. 

 

 이렇게 원하는 정보를 모두 파악했으므로, 단지의 수인 count를 먼저 출력해 준 후, 연결리스트를 순회하며 단지 내 가구수를 순차적으로 출력해 줍니다. 이때 반복문을 다시 쓰지 않기 위해서 저는 메모리 해제까지 함께 해주었습니다. 

 

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

typedef struct LINKED {
    int num;
    struct LINKED *next;
} Linked;

char **makeMap(int N) {
    char **map = (char **)malloc(sizeof(char *) * N);
    if (map == NULL) return NULL;
    
    for (int i = 0; i < N; i++) {
        map[i] = (char *)malloc(sizeof(char) * (N + 1));
        if (map[i] == NULL) {
            for (int j = 0; j < i; j++) free(map[j]);
            return NULL;
        }
        scanf("%s", map[i]);
    }
    return map;
}

Linked *makeElem(int num, Linked *next) {
    Linked *elem = (Linked *)malloc(sizeof(Linked));
    if (elem == NULL) return NULL;
    
    elem->num = num;
    elem->next = next;
    return elem;
}

int findHouse(int x, int y, int N, char ***map) {
    int count = 1;
    
    if (x > 0 && (*map)[x-1][y] == '1') {	// 현재 위치의 위에 집이 있는지
        (*map)[x-1][y] = '0';
        count += findHouse(x-1, y, N, map);
    }
    if (y > 0 && (*map)[x][y-1] == '1') {	// 현재 위치의 왼쪽에 집이 있는지
        (*map)[x][y-1] = '0';
        count += findHouse(x, y-1, N, map);
    }
    if (x < (N-1) && (*map)[x+1][y] == '1') {	// 현재 위치의 아래에 집이 있는지
        (*map)[x+1][y] = '0';
        count += findHouse(x+1, y, N, map);
    }
    if (y < (N-1) && (*map)[x][y+1] == '1') {	// 현재 위치의 오른쪽에 집이 있는지
        (*map)[x][y+1] = '0';
        count += findHouse(x, y+1, N, map);
    }
    
    return count;
}

int main() {
    int N;
    scanf("%d", &N);
    
    char **map = makeMap(N);
    if (map == NULL) return 1;
    
    Linked *head = makeElem(0, NULL);
    if (head == NULL) return 1;
    int count = 0;
    for (int x = 0; x < N; x++) {
        for (int y = 0; y < N; y++) {
            if (map[x][y] == '0') continue;
            
            map[x][y] = '0';
            count++;
            int num = findHouse(x, y, N, &map);
            if (head->num == 0) head = makeElem(num, NULL);
            else if (head->num > num) head = makeElem(num, head);
            else {
                Linked *curr = head;
                while (curr->next && (curr->next->num < num)) curr = curr->next;
                curr->next = makeElem(num, curr->next);
            }
        }
    }
    printf("%d\n", count);
    
    Linked *f;
    while (head) {
        printf("%d\n", head->num);
        f = head;
        head = head->next;
        free(f);
    }
    free(head);
}