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

문제 출처 : www.acmicpc.net/problem/11067 

11067번: 모노톤길

내 풀이

import sys

input = sys.stdin.readline

t = int(input())

for i in range(t):   
    n = int(input())    
    answer = [[0, 0]]
    dic = {}
    
    for j in range(n):
        x, y = map(int, input().split())
        if x not in dic:
            dic[x] = list()
        dic[x].append(y)
        
    sdic = sorted(dic.items())

    for j in range(len(sdic)):
        sdic[j][1].sort()
        if answer[-1][1] != sdic[j][1][0]:
            sdic[j][1].sort(reverse = True)   
        for k in range(len(sdic[j][1])):
            answer.append([sdic[j][0], sdic[j][1][k]])
            
    m = list(map(int, input().split()))

    for j in range(1, len(m)):
        print(*(answer[m[j]]))

설명

시간 제한이 5초로 굉장히 널널한 편이었다.

아마 일단 구현만 해낸다면 대부분 통과가 뜨지 않을까 싶다.

 

입구에서 시작해서 출구까지 가는동안 서쪽으로 이동하지 않는다는 조건이 있다.

이는 좌표로 표현했을 때, x좌표는 절대로 작아지지 않는다는 뜻이다.

그렇다면 풀이는 간단하다.

같은 x좌표에 있는 지점부터 모두 방문한 후에 같은 y축(높이)에 있는 다음 x좌표로 넘어가는 방식으로 계속가면 된다.

이를 한번에 해결하기 위해 우선 answer[]라는 리스트에 [0,0]을 넣어 줬다.

다음에는 입력받는 지점의 위치들을 dict에 같은 x끼리 모아 저장해 리스트로 뽑아줬다.

후에는 각 x에 있는 지점들을 정렬한 후에 각 x위치에 있는 지점들간에 앞,뒤 y의 크기가 같은지 체크 후에

같으면 그대로 answer에 넣어주고 다르다면 반대로 뒤집어서 answer에 넣어 준 후에

해당 위치를 print했다.

결론

사실 그럼에도 시간초과가 날 수도 있을까봐 채점하면서 상당히 조마조마했다.

다른 코드들도 살펴보려했지만 파이썬으로 풀이를 한 경우가 거의 없었고 풀었다 하더라도 크게 코드의 차이가 없어

시간들이 비슷하게 걸렸었다.

dict와 item()을 이용한 정렬이 어떤 기능인지와 함께 어떻게 정렬해나갈지만 생각해낸다면 풀 수 있는 문제였던 것 같다.