Codeforces Round #812 (Div. 2) - Traveling Salesman Problem 링크
(2022.08.29 기준 Difficulty *800)

문제

(0, 0)에서 시작해서 x축 또는 y축 위에 있는 상자들을 모두 모아서 (0, 0)으로 다시 돌아올 때의 최소 이동 수

알고리즘

풀이에서 후술하겠지만, 축마다 가장 값이 작은 점과 큰 점으로 갔다 오면 되므로 그리디라고 할 수 있다. (그리디이긴 한데, 너무 간단한 구현 문제라고 해도 무방할 듯?)

풀이

모든 상자는 축 위에 있으므로 만약 x가 최소값인 좌표를 가지는 상자를 가지러 가기만 해도 x가 음수인 좌표의 상자 모두 쓸어 담을 수 있다.

만약 빨간 점이 상자가 있는 위치이면 파란색 체크가 되어 있는 곳까지 가면 다 쓸어 담을 수 있다. 이런 방식으로 축마다의 최소값과 최대값으로 왔다 갔다 하면 된다.

코드

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    minX = maxX = minY = maxY = 0
    for __ in range(int(input())): # x, y를 입력받을 때마다 최소값과 최대값을 갱신
        x, y = map(int, input().split())
        if x < minX:
            minX = x
        elif maxX < x:
            maxX = x
        if y < minY:
            minY = y
        elif maxY < y:
            maxY = y
    print((maxX - minX + maxY - minY) * 2)

여담

난 멍청하다.
x축이나 y축 위에 상자가 있다는 조건을 안보고, 진짜 외판원 순회처럼 풀려다가 못풀었다..ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

앞으로는 문제를 유심히 잘 읽고 풀어야 겠다.