[백준/C언어] 11651번 - 좌표 정렬하기 2

백준 웹사이트 "11651번 - 좌표 정렬하기 2" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

11651번: 좌표 정렬하기 2

---

소스 코드

#include <stdio.h>

void merge_sort(int (*arr)[2], int index, int len);
void merge(int (*arr)[2], int l_index, int r_index, int l_len, int r_len);
int compare(int (*a)[2], int (*b)[2]);

int main(void){
    int N;
    scanf("%d", &N);

    int coordinates[N][2];
    for(int i=0; i<N; i++){
        scanf("%d %d", &coordinates[i][0], &coordinates[i][1]);
    }
    
    //Merge Sort
    merge_sort(coordinates, 0, N);

    //출력
    for(int i=0; i<N; i++){
        printf("%d %d\n", coordinates[i][0], coordinates[i][1]);
    }
}

void merge_sort(int (*arr)[2], int index, int len){
    // Base Case
    if(len==1){
        return;
    }

    // Recursive Case
    // 1. arr을 반으로 나눈다
    int left = index;
    int right = index + len/2;
    int left_len = len/2;
    int right_len = len - len/2;

    // 2. 왼쪽, 오른쪽을 각각 merge_sort 한다
    merge_sort(arr, left, left_len);
    merge_sort(arr, right, right_len);

    // 3. 왼쪽, 오른쪽을 merge 한다
    merge(arr, left, right, left_len, right_len);
}

void merge(int (*arr)[2], int l_index, int r_index, int l_len, int r_len){
    //printf("merge: %d %d\n", l_index, r_index);
    // 1. 임시 배열 선언
    int temp[l_len+r_len][2];
    int count = 0;
    
    // 2. 왼쪽, 오른쪽의 가장 작은 수 비교
    int l_count = 0;
    int r_count = 0;
    while(1){
        int left = l_index + l_count;
        int right = r_index + r_count;
        if(compare(&arr[left], &arr[right])){ //arr[left] < arr[right]이면 1
            temp[count][0] = arr[left][0];
            temp[count][1] = arr[left][1];
            count++;
            l_count++;
        }
        else{
            temp[count][0] = arr[right][0];
            temp[count][1] = arr[right][1];
            count++;
            r_count++;
        }

    // 3. 왼쪽이나 오른쪽의 끝에 도달하면 break
        if(l_count==l_len || r_count==r_len){
            break;
        }
    }

    // 4. 남은 요소 temp로 복사
    if(l_count==l_len){ // 오른쪽을 복사
        while(count<l_len+r_len){
            temp[count][0] = arr[r_index+r_count][0];
            temp[count][1] = arr[r_index+r_count][1];
            count++;
            r_count++;
        }
    }
    else{               // 왼쪽을 복사
        while(count<l_len+r_len){
            temp[count][0] = arr[l_index+l_count][0];
            temp[count][1] = arr[l_index+l_count][1];
            count++;
            l_count++;
        }
    }

    // 5. arr에 임시배열 복사
    for(int i=l_index; i<l_index+l_len+r_len; i++){
        arr[i][0] = temp[i-l_index][0];
        arr[i][1] = temp[i-l_index][1];
    }
}

int compare(int (*a)[2], int (*b)[2]){  //a<b이면 1 반환
    if((*a)[1]<(*b)[1]){
        return 1;
    }
    else if((*a)[1]==(*b)[1]){
        if((*a)[0]<(*b)[0]){
            return 1;
        }
    }
    return 0;
}

---

문제 풀이

  11650번 문제와 거의 동일한 문제입니다. 11650번에서는 x좌표로 우선 정렬시키고 x좌표가 같을 경우 y좌표로 정렬시켰다면, 11651번에서는 y좌표로 우선 정렬시키고 같을 경우 x좌표로 정렬시킵니다. 나머지 문제 조건, 좌표들의 범위 등등은 모두 동일하기 때문에, 사용되는 코드 역시 거의 동일합니다.

  11650번 문제와 11651번 문제의 차이점에 착안하면, 결국 다른 것은 '크다'의 정의입니다. 11650번에서는 x좌표가 큰 쪽이 '큰 좌표'인 것이고, 11651번에서는 y좌표가 큰 쪽이 '큰 좌표'인 셈이죠. 따라서 좌표들의 대소관계를 비교하는 'compare' 함수만 수정하면 목적에 맞게 코드를 바꿀 수 있습니다. Line 102의 compare 함수에서, (*a)[0]과 (*b)[0]은 각각 a와 b의 x좌표이고, (*a)[1]과 (*b)[1]은 각각 a와 b의 y좌표입니다. 이들을 바꿔 비교하는 순서를 'x좌표→y좌표'에서 'y좌표→x좌표'로만 수정하면, 문제는 쉽게 풀립니다.

  아래는 백준 웹사이트 "11650번 - 좌표 정렬하기" 문제풀이 링크입니다. 전체 코드에 대한 더 자세한 설명이 궁금하면 참고해주세요!

[백준/C언어] 11650번 - 좌표 정렬하기