[파이썬/Python] 백준 2564번: 경비원

숨·2024년 9월 27일

코테

알고리즘 문제 풀이

목록 보기

87/105

📌 문제 : 백준 2564번

📌 문제 탐색하기

n, m : 블록 가로의 길이, 세로의 길이 $(1 ≤ n, m ≤ 100)$
nums : 상점의 개수 $(1 ≤ nums ≤ 100)$

동근이 위치와 각 상점 간 최단 거리의 합을 구하는 문제이다.

문제 풀이

⭐️ 블록 설명

n ⅹ m의 블록에서 중간에 가로지를 수 있는 통로 ❌

블록 둘레에 상점들이 위치

이동 시, 둘레 따라 이동

상점 위치, 동근 위치는 블록 꼭짓점 ❌

위치의 의미

첫째 수 : 상점 위치 방향

1 : 북쪽

2 : 남쪽

3 : 서쪽

4 : 동쪽

둘째 수 : 경계로부터의 거리

북 & 남 : 왼쪽으로부터

동 & 서 : 위쪽으로부터

블록의 경계선을 따라 이동해야 하므로 시계 방향, 반시계 방향 2가지 이동 방법이 있다.
→ 2가지의 방법으로 각 상점까지의 거리를 계산하고 더 짧은 길이를 더해주면 될 것이다.
(반시계방향 계산의 용이함을 위해 전체 둘레 길이를 미리 계산)

블록의 맨 위 왼쪽 위치를 (0, 0)으로 생각하고 이 위치부터 각 상점의 위치까지의 거리를 계산한다.
→ 방향을 의미하는 첫째 수에 따라 거리 계산 방식을 다르게 해야 한다.

for문을 통해 위치 정보에 하나씩 접근해서 첫째 수가 의미하는 방향을 거리로 바꾸어 상점 위치를 계산한다.
1 (북) : 둘째 수 그대로
2 (남) : 시계방향으로 왼쪽 아래 꼭짓점에 온 후 둘째 수 빼기
3 (서) : 시계방향으로 왼쪽 위 꼭짓점에 온 후 둘째 수 빼기
4 (동) : 시계방향으로 오른쪽 위 꼭짓점에 온 후 둘째 수 더하기

거리로 바꾸는 과정을 동근이 위치, 각 상점의 위치에 대해서 진행할 것이므로 이용하기 편하도록 따로 함수화해준다.

동근이 위치와 각 상점 위치를 거리로 변환한 후 그 차이를 계산하면 시계 방향으로 이동했을 경우의 거리를 얻을 수 있다..
→ 이 값을 전체 둘레 합에서 빼서 반시계 방향 이동 시 거리를 구한다.
→ 두 값 중 더 최소를 최단 거리 누적합에 계산하면 된다.

가능한 시간복잡도

상점 위치 입력 → $O(nums)$
거리 계산 → $O(nums)$

최종 시간복잡도
$O(nums)$ 가 되어 최악의 경우 $O(100)$ 이 되는데 이는 1초내 연산 가능하다.

알고리즘 선택

각 상점 위치를 기준점으로부터의 거리로 계산해서 최단 거리 찾기

📌 코드 설계하기

거리 변환 함수 정의
필요한 입력 받기
전체 둘레 미리 계산
동근의 위치 거리 변환
최단 거리 합 저장 변수 정의
각 상점에 대해 거리 계산 후 최단거리 계산
결과 출력

📌 시도 회차 수정 사항

1회차

예제 입력 1에 대한 답으로 30만 나왔다.
변수들의 이름 의미가 비슷하다보니 변수를 잘못 적었다.
answer 변수에 최단 거리 합을 담았는데 total_distance라는 전체 둘레를 의미하는 변수를 출력해서 예제 입력1의 둘레인 30이 출력된 것이었다.

📌 정답 코드

import sys

input = sys.stdin.readline


# 거리 계산
def calculate_distance(direction, distance):
    if direction == 1:
        return distance
    elif direction == 2:
        return 2 * n + m - distance
    elif direction == 3:
        return 2 * (n + m) - distance
    elif direction == 4:
        return n + distance


# 블록 가로, 세로 길이 입력
n, m = map(int, input().split())

# 상점 개수 입력
nums = int(input())

# 상점 위치 입력
locations = [list(map(int, input().split())) for _ in range(nums)]

# 동근 위치 입력
start = list(map(int, input().split()))

# 전체 둘레 계산
total_distance = 2 * (n + m)

# 동근 위치 거리 변환
start_distance = calculate_distance(start[0], start[1])

# 최단 거리 합 저장할 변수 정의
answer = 0

# 각 상점에 대해 거리 계산 후 최솟값 찾기
for location in locations:
    store_distance = calculate_distance(location[0], location[1])

    # 시계방향 거리 계산
    distance1 = abs(start_distance - store_distance)
    # 반시계방향 거리 계산
    distance2 = total_distance - distance1

    # 최단 거리 합 선택
    answer += min(distance1, distance2)

# 결과 출력
print(answer)