[백준-파이썬] 11067: 모노톤길

흑흑 ㅠㅠㅠㅠ 드디어 맞았습니다.!!
이 문제는 무슨 알고리즘을 써야할까? 이런 고민보다는..
아 이거 맞겠지 ? ? 이러고 돌렸는데 자꾸 틀렸다..ㅠㅠ

그러다가 이 분의 포스팅을 보고 어디에서 문제가 있었는지 알게 되었다 !!
아.. 이걸 설명하기 전에 아이디어를 쓰겠다!

아이디어 ✨

'입구에서 출구 방향으로 걸어갈 때 동쪽에서 서쪽으로 이동을 전혀 하지 않아도, 즉, 보행자의 현재 위치를 나타내는 좌표의 x축 값이 작아지는 경우가 없이도 출구까지 도달할 수 있다. ' 라고 되어 있다 => 항상 왼쪽(x축이 작은 쪽)에서 오른쪽(x축이 큰 쪽)으로만 간다! X축은 항상 증가하는 쪽으로 가야 한다.
같은 X축에 여러 개의 카페가 있을 수도 있는데, 모두 방문해서 번호를 줘야 한다. 그래서 X축이 같은데 Y축이 다른 카페가 여러 개라면, 이전 것과 Y축이 같은 것부터 순서대로 가야한다. 그래서 그전까지의 X축 위치를 가지고(초기값은 0으로), 같은 X축 위치가 나오면 그런 카페들을 임시 리스트에 넣었다.
그 후 X축이 다른 게 나오면, 그때까지 담아둔 리스트를 순서에 맞게 final_cafes에 배치했다. 이때 그전 Y축과 임시 리스트 첫번째 원소값이 같으면, 그냥 그 방향대로 가면 된다. 그런데 그전 Y축과 임시 리스트 첫번째 원소값이 다르면, 방향이 반대로 가야 한다는 뜻이라서 .sort(reverse=True)를 해주었다.
그러면 final_cafes의 원소들은 카페 순서대로 x, y를 튜플로 가지고 있는 것이다! 그러니까 이를 활용해서 요구하는 카페 번호의 위치를 출력해주면 끝이다.

계속 틀렸던 이유 😥

그 전까지의 x축 위치를 가지고, 같은 x축 위치가 나오면 그걸 리스트에 담아뒀다가 순서에 맞게 배치하는 식으로 코드를 짰다. 맨 처음에는 x축 위치를 0으로 주고 하려고 했다. (1번 카페는 무조건 (0,0)이니까) 그런데!! x축 위치가 0인데 y축이 다른 카페들이 여러 개 나오는 경우를 생각 못했던 것이다.
나는 카페 (x,y)를 튜플로 받아서 sort를 해버렸다. 그러면 (0,0)이 맨 앞에 있을 것이라고 생각했는데, (0,-2) 같은 것도 있었으면 (0,0)보다 (0,-2)가 앞으로 정렬이 되었던 것이다.
코드로 설명하자면..!
final_cafes = [cafes[0]] cur_x, cur_y = cafes[0] same_y = [cafes[0]]
=>
final_cafes = [(-1, 0)] cur_x, cur_y = (-1, 0) same_y = [(-1, 0)]
위에 언급한 포스팅에서 (-1,0)으로 바꾸는 부분을 참고해서 바꾸니까 성공했다 ㅠㅠ

코드 👩‍💻

import sys

input = sys.stdin.readline

# 항상 서쪽 -> 동쪽으로만 간다! 반대로 안감. (X 축 늘어나는 방향으로만 가야 함)
# 같은 X축에 여러 개의 카페가 있을 수도 있는데, 모두 방문해야 함! (X 같은 것이 여러 개라면, 이전 것과 y축 차이가 적은 것부터 가기)

T = int(input())
for _ in range(T):
    N = int(input())
    cafes = list(tuple(map(int, input().split())) for _ in range(N))
    # 정렬: X축 낮은 순서대로
    cafes.sort()

    # print(cafes)

    final_cafes = [(-1, 0)]
    cur_x, cur_y = (-1, 0)
    same_y = [(-1, 0)]  # 같은 X축에 다른 Y축인 카페가 여러 개라면 리스트에 저장
    i = 0
    while i < N:
        if cur_x == cafes[i][0]:
            same_y.append(cafes[i])

        else:
            # X축이 같은 카페를 배치하기
            if final_cafes[-1][1] != same_y[0][1]:  # 만약 순서가 맞지 않으면 거꾸로 해주기
                same_y.reverse()
            final_cafes.extend(same_y)
            same_y = [cafes[i]]
            cur_x, cur_y = cafes[i]
        i += 1

    # 마지막 부분을 final_cafes에 안 넣었으면
    if same_y[0] not in final_cafes:
        if final_cafes[-1][1] != same_y[0][1]:  # 만약 순서가 맞지 않으면 거꾸로 해주기
            same_y.sort(reverse=True)
        final_cafes.extend(same_y)

    # print(final_cafes)

    # 출력할 카페 번호 받아오기 
    where_cafes = list(map(int, input().split()))

    # 각각 카페 위치 출력하기 (맨 처음 꺼는 몇 개인지 하는 거라서 빼고!)
    for i in range(1, len(where_cafes)):
        print(*final_cafes[where_cafes[i]+1])