문제 출처 : https://www.acmicpc.net/problem/2564
난이도 : 실버 1
문제 파악
이 문제는 직사각형의 테두리 위에 위치한 여러 상점들과
동근이의 위치가 주어졌을 때,
동근이가 모든 상점까지 이동해야 하는
최단 거리의 합을 구하는 문제다.
처음 보면 단순 거리 계산처럼 보인다.
하지만 중요한 조건이 있다.
- 이동은 직사각형 내부를 가로질러 갈 수 없다.
- 반드시 테두리를 따라 이동해야 한다.
- 시계 / 반시계 방향 중 더 짧은 거리를 선택한다.
시행 착오
처음에는 각 위치를 (x, y) 좌표로 변환해서
맨해튼 거리로 계산하려고 했다.
예를 들어,
- 북쪽이면 y = 0
- 남쪽이면 y = h
- 서쪽이면 x = 0
- 동쪽이면 x = w
이렇게 좌표로 바꿔서 계산하려고 했는데,
문제가 있었다.
테두리를 따라 이동해야 하는데,
단순 맨해튼 거리로는
시계 / 반시계 중 어떤 경로가 더 짧은지를
정확히 계산할 수 없다.
결국 좌표 접근은
케이스 분기가 복잡해지고,
논리가 꼬이기 시작했다.
이 문제의 핵심은
“2차원처럼 보이지만 사실은 1차원 문제”라는 점이었다.
해결 아이디어
2차원 매트릭스를 1차원 선형 좌표로 펼치기
직사각형의 테두리를 한 바퀴 도는
1차원 선형 좌표로 변환한다.
사각형 둘레는
P = 2 * (w + h)
각 위치를
좌상단을 0으로 잡고
시계 방향으로 쭉 펼친 좌표 s 로 변환한다.
방향 벡터는 다음과 같다.
1 북
2 남
3 서
4 동
변환 공식은 다음과 같다.
- 북(1) : s = l
- 동(4) : s = w + l
- 남(2) : s = w + h + (w - l)
- 서(3) : s = 2w + h + (h - l)
이렇게 하면
모든 위치가 0 ~ P 사이의 하나의 숫자로 표현된다.
이제 두 점 사이의 거리 계산은 간단하다.
diff = |a - b|
최단거리 = min(diff, P - diff)
diff는 한 방향 거리,
P - diff는 반대 방향 거리다.
즉,
시계 / 반시계 모두 자동으로 커버된다.
코드
import sys
input = sys.stdin.readline
w, h = map(int, input().split())
N = int(input())
stores = [tuple(map(int, input().split())) for _ in range(N)]
dg_d, dg_l = map(int, input().split())
P = 2 * (w + h)
def to_scalar(d, l):
if d == 1: # 북
return l
elif d == 4: # 동
return w + l
elif d == 2: # 남
return w + h + (w - l)
else: # 서
return 2 * w + h + (h - l)
def shortest_distance(a, b):
diff = abs(a - b)
return min(diff, P - diff)
dg_s = to_scalar(dg_d, dg_l)
total = 0
for d, l in stores:
s = to_scalar(d, l)
total += shortest_distance(dg_s, s)
print(total)한 줄 정리
2차원 matrix에 좌표를 찍어 최단거리를 구하려고 했다가 실패했다.
사각형의 둘레만을 거리로 삼을 수 있다면, 사각형의 둘레를 쭉 펴서 1차원 선이라고 생각해보자.
