[알고리즘] 백준 파이썬 2564 경비원

📍 문제 탐색하기

동근이는 직사각형 모양의 블록 경계를 따라 상점의 위치로 이동해야 한다. 블록 중간을 가로질러 갈 수 없기 때문에, 블록의 가장자리를 따라 시계 방향 또는 반시계 방향으로만 이동해야 한다.
주어진 상점들과 동근이의 위치를 기준으로, 최단 거리의 합을 계산하는 것이 목표이다.

---

문제 조건 분석

• 입력 조건
  1. 첫째 줄: 블록의 가로 길이 w와 세로 길이 h
  2. 둘째 줄: 상점의 개수 n
  3. 이후 n개의 줄: 상점의 위치 (방향, 거리)
  4. 마지막 줄: 동근이의 위치 (방향, 거리)
• 방향 정보 (1~4)
  • 1: 블록의 북쪽 (북쪽 기준 왼쪽에서의 거리)
  • 2: 블록의 남쪽 (남쪽 기준 왼쪽에서의 거리)
  • 3: 블록의 서쪽 (서쪽 기준 위쪽에서의 거리)
  • 4: 블록의 동쪽 (동쪽 기준 위쪽에서의 거리)

---

가능한 해결 전략

1. 블록을 일직선으로 펼치기 (펼친 좌표 변환)
   • 블록을 둘레 길이의 일직선으로 생각하고, 동근이와 상점의 위치를 일차원 좌표로 변환.
   • 두 위치의 거리 = 절댓값 차이와 전체 블록 둘레에서의 반대 방향 거리 중 최솟값 선택.
2. 이동 거리 계산 방법
   • 블록의 전체 둘레: 2(w+h)
   • 시계 방향 거리와 반시계 방향 거리 비교 후 최단 거리 선택.

---

📍 코드 설계하기

알고리즘 아이디어

1. 블록의 둘레 계산: 2(w+h)
2. 상점 및 동근이의 위치를 펼친 좌표로 변환.
3. 각 상점과 동근이 간의 최단 거리 계산.
4. 모든 거리의 합을 출력.

---

📍 시도 회차 및 수정 사항

첫번째 시도

import sys
input = sys.stdin.readline

width, height = map(int, input().split())
n = int(input())

store = []

for _ in range(n):
    store.append(list(map(int, input().split())))
    
d_dir, d_length = map(int, input().split())    

total_distance = 0
for i in range(n):
    distance = 0
    dir, length = store[i][0], store[i][1]
    
    # 북쪽 (1)
    if d_dir == 1:
        if dir == 1:
            distance = abs(length - d_length)
        elif dir == 2:
            distance = min((d_length + height + length), (width - d_length + height + width - length))
        elif dir == 3:
            distance = d_length + length
        else:  # 동쪽
            distance = (width - d_length) + length

    # 남쪽 (2)
    elif d_dir == 2:
        if dir == 1:
            distance = min((d_length + height + length), (width - d_length + height + width - length))
        elif dir == 2:
            distance = abs(length - d_length)
        elif dir == 3:
            distance = d_length + (height - length)
        else:  # 동쪽
            distance = (width - d_length) + (height - length)

    # 서쪽 (3)
    elif d_dir == 3:
        if dir == 1:
            distance = d_length + length
        elif dir == 2:
            distance = (height - d_length) + length
        elif dir == 3:
            distance = abs(length - d_length)
        else:  # 동쪽
            distance = min(d_length + width + length, (height - d_length) + width + (height - length))

    # 동쪽 (4)
    elif d_dir == 4:
        if dir == 1:
            distance = d_length + (width - length)
        elif dir == 2:
            distance = (height - d_length) + (width - length)
        elif dir == 3:
            distance = min(d_length + width + length, (height - d_length) + width + (height - length))
        else:  # 동쪽
            distance = abs(length - d_length)

    total_distance += distance

print(total_distance)

정답이긴 하지만 정말 노가다 코드.. 풀면서도 이걸 원하는게 아닐텐데.... 했다. 

따라서 이후 펼친 좌표 형식으로 수정해주었다.

import sys
input = sys.stdin.readline

width, height = map(int, input().split())
n = int(input())

store = []

def cal_distance(direction, distance):
    if direction == 1: # 북
        return distance
    elif direction == 2: # 남
        return width + height + (width - distance)
    elif direction == 3: # 서
        return 2 * width + height + (height - distance)
    elif direction == 4: # 동
        return width + distance

for _ in range(n):
    dir, length = map(int, input().split())
    store.append(cal_distance(dir, length))
    
d_dir, d_length = map(int, input().split())    
d_distance = cal_distance(d_dir, d_length)

total = 2 * (width + height)

total_distance = 0
for s_distance in store:
    min_distance = min(abs(d_distance - s_distance), total - abs(d_distance - s_distance))
    total_distance += min_distance

print(total_distance)