Monotone Walkway ( ACM-ICPC 교내 예선 )

내가 푼 마지막 문제다. 이번엔 그림도 있다. 장잉정신을 발휘해서 그리려고 보니 keynote가 자동으로 자리도 맞춰주는 기능들이 있어서 꽤 편하게 그릴 수 있었다. 격자로 뭔가 할게 있다면 키노트를 추천한다.

---

[문제]
제주 올레길 코스로 유명한 산책로가 있다. 산책로의 입구는 산책로에서 가장 서쪽에 위치하고 있다. 이 산책로는 단순 경로이며 수평 구간과 수직 구간으로만 구성되어 있어 모든 코너에서 90도 각도로 왼쪽 또는 오른쪽으로 회전만 할 수 있다. 또한 입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 이동을 전혀 하지 않아도 즉, 보행자의 현재 위치를 나타내는 좌표의 x축 값이 작아지는 경우가 없이도 출구까지 도달할 수 있다. 그래서 이 산책로를 모노톤길이라고 부른다. 아래 그림은 모노톤길의 예를 보여준다.

이 산책로에는 n개의 카페가 곳곳에 들어서 있다. 특히 입구와 출구 그리고 모든 코너에는 카페가 들어서 있다. 올레길 코스 관리자인 김씨는 이 산책로에 들어서 있는 모든 카페들의 위치 좌표를 가지고 있다. 입구 좌표는 항상 원점 (0,0)이다. 그는 이들 카페에 1부터 n까지의 일련번호를 붙이려고 한다. 입구의 카페는 1번, 그 다음부터는 길을 따라가면서 만나는 순서대로 번호를 배정하다. 입구에서 출구로 갈 때 카페 A를 카페 B보다 먼저 만나게 된다면 A에는 B보다 더 작은 번호를 배정한다. 따라서 위 그림의 산책로에서 좌표 (3,1)에 위치한 카페의 번호는 5이고, 좌표 (9,0)에 위치한 카페는 14번이고, 출구의 카페는 17번이다. 그는 산책로를 직접 걷지 않고 카페의 좌표들만으로 이 작업을 수행하고 싶어한다. 그를 도와서 카페에 번호를 붙이는 작업을 수행하는 프로그램을 작성하시오.

[입력]
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 개수 T가 정수로 주어진다. 각 테스트 데이터의 첫 번째 줄에는 카페의 수를 나타내는 정수 n (2<=n<=100,000)이 주어진다. 그 다음 n개의 줄에는 각 줄마다 각 카페의 좌표 (x,y)를 나타내는 두 개의 정수 x와 y가 주어진다. (0<=x<=100,000), (-100,000<=y<=100,000) 입구 좌표는 항상 (0,0)이다. 어떤 두 카페도 동일한 좌표를 가지는 경우는 없다. 마지막 줄에는 정수 m (1<=m<=10)과 m개의 정수가 주어진다. m 개의 각 정수는 1 이상 n 이하로서 카페의 번호를 나타낸다.

[출력]
출력은 표준출력을 사용한다. 각 테스트 데이터에 대해, 카페 번호로서 주어진 m개의 정수에 대한 답을 순서대로 한 줄에 하나씩 출력한다. 정수 k에 대한 답은 번호가 k 인 카페의 좌표 (x,y)를 나타내는 두 개의 정수 x와 y이다.

[예시]

입력 예제	출력 예제
2 17 3 3 5 3 11 2 9 2 2 1 3 1 5 1 0 0 1 0 2 0 9 0 11 -1 9 -3 6 -1 7 -1 7 -3 5 -1 3 5 14 17 4 0 0 0 1 1 1 1 0 5 1 4 1 3 1	3 1 9 0 11 -1 0 0 1 0 0 0 1 1 0 0

def cmp_by_x( a, b ):
    return cmp( a[0], b[0] )
def cmp_by_y( a, b ):
    return cmp( a[1], b[1] )
 
# input the number of test cases
T = input()
for _ in xrange( T ):
    num_cafe = input()
    cafe = list()   
    # store cafe location[x,y] into cafe list
    for i in xrange( num_cafe ):
        cafe.append( map(int, raw_input().split()) ) # input x, y
 
    order = map(int, raw_input().split())   # input orders
    num_order = order.pop(0)                # num of output line
 
    cafe.sort( cmp=cmp_by_x )               # sorting to make x-chunks
 
    previous_y = 0    # initial y value
    # previous_y is y value of previous x-chunk
 
    for left_idx in xrange( num_cafe ) :
        right_idx = left_idx+1
        while cafe[left_idx][0] == cafe[right_idx][0] :
            right_idx += 1
            if right_idx < num_cafe:
                break
 
        if right_idx != left_idx+1:
            # copy the partial cafe list
            temp_lst = cafe[left_idx:right_idx]
            
            if cafe[left_idx+1][1] > previous_y:
                temp_lst.sort( cmp=cmp_by_y, reverse=False )
            elif cafe[right_idx-1][1] > previous_y:
                temp_lst.sort( cmp=cmp_by_y, reverse=False )
            else :
                temp_lst.sort( cmp=cmp_by_y, reverse=True )
 
            # restore partial data
            cafe[left_idx : right_idx] = temp_lst[:]    
 
        previous_y = cafe[left_idx][1]        # mark for next iteration
 
    for i in xrange( num_order ):
        # print x y
        print "%d %d"%(cafe[order[i]-1][0], cafe[order[i]-1][1])

이전 포스팅과 마찬가지로 코드 자체에 주석으로 설명을 거의 넣어두었다. 알고리즘 상으로 의문이 들 만한 x, y 정렬 부분을 우리말로 풀어쓰고 글을 마치겠다.

우선 생각난 방법은 x값 기준으로 정렬하는 것이다. 이렇게 되면 x값들이 같은 묶음이 생기지만 부족하다. 이대로만 따라가면 y값들이 아직 정확한 규칙으로 정렬된 것이 아니므로 길을 따라갈 수가 없다. x값 기준으로 정렬한 결과를 가지고 생각해보면 같은 x값을 공유한 카페가 여럿일때 y값에 따라 서로 순서를 정할 필요가 있다. 그래야 올레길 위에 놓은 카페들을 순서대로 나열할 수 있기 때문이다. 실제로 올레길을 걷는 사람이 되어 생각해보면 어떤 때는 y값이 감소하는 방향으로 걸을 것이고, 어떤 때는 y값이 증가하는 방향으로 걸을 것이다. 따라서 같은 x값을 공유한 묶음 안에서 y값을 기준으로 내림차순으로 정렬할 때도 있고 오름차순으로 정렬할 때도 있다. 언제 어떤 기준을 이용해 정렬할지 생각해보려면 bucket sort개념을 이용한다.

나는 previous_y라는 변수를 써서 y값 정렬에 이용할 것이다. 34번 줄을 잘 살펴보길 바란다. previous_y는 반복문 안에서 y값 정렬시에 오름차순으로 할지 내림차순으로 할지 결정해주는 역할을 한다. x값 기준으로 정렬한 후 올레길을 걸어가면서 x값 증가 방향으로 나아가면서 새로운 카페들을 만난다고 생각해보자. 어떤 n번째 묶음을 제대로 정렬한 다음 n+1번째 묶음을 정렬할 순서가 되면 n+1 묶음의 모든 y값들은 n번째 묶음의 모든 y값들보다 작거나 같거나, 혹은 크거나 같을 것이다. 즉 y값을 가져와서 이들 중 하나와 비교해보면 크거나 같거나 작거나 같을테니 이를 이용한다. n번째 묶음의 마지막 카페의 y값을 알고서 n+1번째 묶음의 y값과 비교해서 정렬할 수 있게된다. 그래서 바로 이전 반복에 쓰인 y값을 previous_y에 기억시킨 것이다.

(아이고 말로 풀어쓰기 참 어렵다ㅜㅜ)