[ICPC] Monotone Walkway(2015 대전 예선)

[ICPC] Monotone Walkway(2015 대전 예선)

Monotone Walkway

이번 ICPC 예선 문제이다. 예선 문제들 중 쉬운 문제였으며 유사한 문제가 많이 존재한다.

문제 요약

첫 줄에는 테스트 케이스 개수가 주어진다. 각 테스트 케이스의 첫 줄에는 좌표의 개수가 주어지고, 개수 만큼의 좌표가 주어진다. 마지막 줄에는 출력해야 할 카페 좌표의 개수와 순서가 주어진다. 각 순서의 카페 좌표를 출력하면 된다.

풀이

- 좌표를 저장할 자료구조를 정한다. 카페 좌표(x, y)는 같은 순서를 가져야 함을 명심한다.

- 카페 좌표들의 x를 기준으로 오름차순 정렬한다. x가 같은 좌표들은 y 기준 오름차순 정렬한다.

- (0,0)부터 마지막 카페까지 순차적으로 가면서, 바로 전 카페와 지금 위치한 카페의 좌표를 비교한다. [그림 1]을 보면 바로 전 카페와 지금 카페 좌표가 x, y 둘 중 하나는 같아야 길이 이어진다. 따라서 x, y 둘 다 다른 지점을 찾고 그 지점의 구간을 찾아 y 기준 내림차순으로 정렬한다.

간단히 정리하면,

맨 왼쪽 열이 x 기준 오름차순(x 같을 경우 y 기준 오름차순) 정렬한 결과이다.

두번째 열은 설명하기 위해서 복사한 열로 왼쪽 열과 같은 열이다. 두 번째 열의 좌표들을 머리 속으로 그려보면 위의 박스에서 길이 끊어지는 것을 알 수 있다. x나 y가 같아야 직선으로 이어질 수 있기 때문이다. 그러면 이어지지 않은 부분을 이어주면 되는데, 그 방법은 아주 간단하다. 이어지지 않는 곳의 두번째 x값을 가진 구간을 반대(내림차순)로 정렬하면 된다.

세번째 열은 해당 구간을 내림차순으로 정렬한 결과 이다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
// 입력가능한 최대 카페 수
#define MAX 100002
 
// 카페 좌표 정보를 가지고 있는 구조체 배열
struct Node{
    int x, y;
}node[MAX];
 
// sort 함수 compare 함수
// 두 node의 x가 같으면 y 기준 오름차순 정렬, x가 다르면 x 기준 오름차순 정렬
// x 기준 오름차순으로 정렬이 되는데 x값이 같은 노드의 경우 y값 오름차순으로 정렬
int compare(const Node &a, const Node &b){
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}
 
// sort 함수 compare 함수
// 두 node의 y값을 내림차순으로 정렬
int compare2(const Node &a, const Node &b) {
    return a.y > b.y;
}
 
int main()
{
    FILE *inFile;
    inFile = fopen("input.txt", "r");
    int testCase, n, m;
 
    for (fscanf(inFile, "%d", &testCase); testCase--; )
    {
        fscanf(inFile, "%d", &n);
 
        for (int i=0; i<n; ++i)
            fscanf(inFile, "%d%d", &node[i].x, &node[i].y);
 
        // x 기준 오름차순 정렬(x가 같은 경우 y 기준 오름차순 정렬)
        sort(node, node+n, compare);
 
        // 1차 정렬된 카페 구조체 배열을 처음 부터 끝까지 탐색한다.
        for (int i=0; i<n; )
        {
            // i는 구간 시작, t는 구간 종료 인덱스를 나타내기 위해 사용한다.
            int t=i;
 
            // 전 카페 좌표와 현재 카페 좌표의 x가 같은 경우 t를 증가시킨다.
            // 달라지면 반복문에서 빠져 나온다.
            for (int j=i+1; j<n; ++j)
            {
                if(node[i].x == node[j].x)
                    t=j;
                else
                    break;
            }
 
            // 구간 시작 인덱스와 구간 종료 인덱스가 다르다면,
            // 즉, 같은 x를 가진 구간이 있다면...
            // 구간 시작 바로 전 카페 좌표의 y와 구간 시작 카페 좌표의 y가 다르다면,
            // 길이 끊어진 것이므로 y 기준 내림차순으로 정렬해서 길을 이어준다.
            if (i != t) {
                if (node[i-1].y != node[i].y)
                    sort(node + i, node + t+1, compare2);
                i = t+1;
            }
            else
                ++i;
        }
 
        // 출력 부분
        for (fscanf(inFile, "%d", &m); m--;)
        {
            int k;
            fscanf(inFile, "%d", &k);
            printf("%d %d\n", node[k-1].x, node[k-1].y);
        }
    }
 
    fclose(inFile);
    return 0;
}

정리

정렬 함수를 이해할 수 있는 좋은 문제였다. 물론 정렬을 직접 구현해서 사용하고 싶은 사람도 있겠지만 알고리즘 문제 풀 때에는 반드시 라이브러리 함수를 사용할 것을 권한다. 다른 함수들도 표준 함수라면 무조건 사용하는 것이 좋다. 그 이유는 라이브러리 함수를 열어보면 알겠지만 오랫동안 고수들에 의해 최적화된 함수들이다. 직접 만들어서 그 함수들을 능가하기는 정말 쉽지 않다. sort 함수 정렬 기준을 정해주는 compare 함수는 람다식으로 compare 함수 자리에 바로 입력해도 된다. 정렬은 많이 이용되기 때문에, sort 함수나 qsort 함수는 많이 사용해 보는 것이 좋을 듯 하다.