[백준] 2564. 경비원 python

🐳 링크

백준 경비원

🐕 문제

동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다.

예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다.

1번 상점에서 호출이 들어 왔을 때 동근이가 블록을 시계방향으로 돌아 이동하면 이동 거리가 12가 된다. 반면 반시계방향으로 돌아 이동하면 이동 거리는 18이 된다. 따라서 동근이가 1번 상점으로 가는 최단 거리는 12가 된다. 마찬가지로 동근이의 위치에서 2번 상점까지의 최단 거리는 6, 3번 상점까지의 최단 거리는 5가 된다.

블록의 크기와 상점의 개수 및 위치 그리고 동근이의 위치가 주어질 때 동근이의 위치와 각 상점 사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.

🐾 풀이 방법

겁나 쉬운 문제같았지만... 은근히 어려웠다 😅
입력이 다음과 같이 주어지는데,

10 5 #가로 세로
3 #상점의 개수
1 4 #방향, 거리
3 2 #방향, 거리
2 8
2 3 #동근이의 방향, 거리

이 문제는 입력에 대한 설명이 중요해서 가져와보았다.

입력

첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄에 하나씩 상점의 위치가 주어진다. 상점의 위치는 두 개의 자연수로 표시된다. 첫째 수는 상점이 위치한 방향을 나타내는데, 1은 블록의 북쪽, 2는 블록의 남쪽, 3은 블록의 서쪽, 4는 블록의 동쪽에 상점이 있음을 의미한다. 둘째 수는 상점이 블록의 북쪽 또는 남쪽에 위치한 경우 블록의 왼쪽 경계로부터의 거리를 나타내고, 상점이 블록의 동쪽 또는 서쪽에 위치한 경우 블록의 위쪽 경계로부터의 거리를 나타낸다. 마지막 줄에는 동근이의 위치가 상점의 위치와 같은 방식으로 주어진다. 상점의 위치나 동근이의 위치는 블록의 꼭짓점이 될 수 없다.

볼드로 된 부분만 제대로 이해하면 될 것 같다.

먼저, 방향(1,2,3,4)에 따라 거리를 할당해야한다.
처음 보면 이해가 안될 수도 있지만.. 최대한 잘 설명해보도록 노력....

위 이미지처럼 각 방향에 따라 거리를 할당한다. 거리를 할당한다는 것의 의미는 다음 이미지를 보면 더 이해가 잘 될 것이므로 일단은 넘어가보자..

거리 계산은 다음과 같은 방식으로 할 것이다.

이게 무슨 뜻이냐 하면은!
동근이가 1번 방향에 위치해있고, 상점이 2번 방향에 위치해있는 경우
첫번째 그림을 참고한다면 동근이의 거리 할당은 (1) 과 같이 되고, 상점의 거리 할당은 (2)와 같이 된다.
따라서 둘 사이의 거리는 첫번째로 (3)의 노란 형광펜과 같은 경우, 즉 abs((1)-(2))와 같다. 두번째로는 (4)의 노란 형광펜과 같은 경우로 1에서 구한 거리를 전체 네모의 둘레에서 빼준다.

자세히 설명을 덧붙이자면,
우리는 전체 네모에서 각 점들 사이의 거리를 구해야한다. 거리를 구할 때에는 두 가지 경우가 존재한다. 가까운쪽, 먼쪽 (어쩌면 같을 수도 있겠지만). 두 가지를 합쳐서 하나의 네모를 만든다고 생각하면 될 것 같다.

따라서 각 경우(동근, 그리고 각 상점)에 대해서 각각 거리 할당을 한뒤, 그 거리들의 차 (path1)와 전체 둘레 - path1 한 경우 중 더 짧은 거리를 전체 total에 누적합 해주는 것이다..!!!

소스코드

import sys
sys.stdin = open("input.txt","rt")

width, height = map(int,sys.stdin.readline().split())
n = int(sys.stdin.readline().strip())
store = list()

def calcDist(dir,dist):
    if dir == 1:
        return dist
    elif dir == 2:
        return width + height + (width - dist)
    elif dir == 3:
        return width + height + width + (height - dist)
    else:
        return width + dist

for _ in range(n+1):
    if _ == n:
        direction, distance = map(int,sys.stdin.readline().split())
    else:
        store.append(list(map(int,sys.stdin.readline().split())))

total = 0
dist1 = calcDist(direction, distance) #동근이의 거리
for i in range(n):
    dist2 = calcDist(store[i][0], store[i][1]) #상점의 거리
    path1 = abs(dist1 - dist2)
    path2 = 2 * width + 2 * height - path1
    total += path1 if path1 < path2 else path2

print(total)