[Python/파이썬] 백준 11067번 모노톤길

https://www.acmicpc.net/problem/11067

코드

import sys
input = sys.stdin.readline


for _ in range(int(input())):
    n = int(input())

    cafes = {}
    for _ in range(n):
        x, y = map(int, input().split())
        if x not in cafes:
            cafes[x] = []
        cafes[x].append(y)

    prev_y = 0
    counted_cafe = []
    for x, y_list in sorted(cafes.items()):
        y_list.sort()
        if y_list[0] != prev_y:
            y_list.reverse()

        for y in y_list:
            counted_cafe.append([x, y])
        prev_y = y_list[-1]

    m, *arr = list(map(int, input().split()))
    for a in arr:
        print(*counted_cafe[a-1])

구현은 어렵지 않은데, 문제 이해가 쪼끔 어려웠던 문제였다. 주어진 조건을 잘 이해해야 하는 문제인 것 같다.

 

모노톤길은 x좌표가 작아지는 방향으로는 이동하지 않는다는 것까지는 대놓고 나와 있어서 x좌표를 기준으로 정렬하는 것은 쉬웠다. 근데 그 다음이 좀 어려웠다.

 

그래서 다시 자세히 문제를 보니 이런 조건이 있었다.

1. 모든 코너에는 카페가 있다.

2. 모든 코너에서 90도 각도로 오른쪽 또는 왼쪽으로만 이동할 수 있다.

 

이 말은 x좌표에서 카페가 존재하는 다음 좌표로 넘어갈 때, 같은 y좌표를 가진 곳에 카페가 있음이 보장됨을 알 수 있다. 그리고 그 카페는 같은 x좌표를 가진 카페들 중에는 가장 작은 y좌표를 갖거나 가장 큰 y좌표를 가질 것이다. 

 

이걸 알고 나니 문제를 쉽게 풀 수 있었다. 앞에서 cafes라는 딕셔너리에 x좌표를 key, 해당 x축에 있는 y좌표들의 리스트를 value로 저장해뒀다. 같은 x축에 속한 y좌표들은 오름차순으로 방문하거나 내림차순으로 방문할 것이다. 오름차순/내림차순을 결정하는 것은 이전 카페의 y좌표이다. 만약 정렬했을 때 첫번째 y좌표가 이전 카페의 y좌표와 같은 정렬 순서를 사용하면 된다.

 

이렇게 모든 x좌표를 처리하고 나면, 모든 카페를 모노톤 경로를 따라 방문한 순서대로 counted_cafe 리스트에 저장할 수 있고, 이를 통해 각 카페의 번호를 알 수 있다.