백준 제비통신 [32337] 파이썬(Python) 코드 + 해설

백준 제비통신 32337번 문제

Solved.ac 난이도 : 실버 1 문제입니다

1. 문제 소개

한양이는 자신이 키우는 M마리의 제비 중 한 마리에게 편지를 묶어 세종이에게 보내고자 한다. 하지만 제비들은 각자 특정한 기울기를 가진 직선 경로로만 이동하며, 이 직선 경로 상에 세종이가 있어야만 편지를 전달할 수 있다.

한양이와 세종이를 놓을 수 있는 N개의 좌표가 주어졌을 때, 제비 통신이 가능하도록 둘을 배치하는 모든 경우의 수를 구하는 문제다. 단, 한양이와 세종이는 같은 좌표에 위치할 수 없다.

2. 문제 해결 방법

이 문제는 두 점을 선택하여 그 사이의 기울기가 주어진 M개의 기울기 중 하나인 경우를 세는 문제다. 하지만 모든 점 쌍을 검사하면 시간 복잡도가 O(N^2)이 되어 제한 시간 내에 해결할 수 없다.

이를 효율적으로 해결하기 위해 다음과 같은 방법을 사용한다:

1. 기울기별로 그룹화: 각 기울기 K에 대해, 모든 점 (xi​,yi​)에 대해 yi​−K×xi​ 값을 계산한다. 이 값이 같은 점들은 기울기 K인 직선 위에 있는 것이다.
2. 해시맵을 이용한 개수 세기: yi​−K×xi​ 값을 키로 하는 해시맵을 만들어, 동일한 키를 가진 점들의 개수를 센다.
3. 쌍의 수 계산: 동일한 직선 위에 있는 점들의 개수가 n일 때, 한양이와 세종이를 선택하는 경우의 수는 순서를 고려하여 𝑛×(𝑛−1)이다.
4. 전체 결과 합산: 모든 기울기 K에 대해 위 과정을 수행하고, 결과를 합산한다.

이렇게 하면 시간 복잡도를 O(M×N)으로 줄일 수 있어 제한 시간 내에 문제를 해결할 수 있다.

3. 백준 32337 제비통신 파이썬(Python) 정답 코드 

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
K_list = list(map(int, input().split()))
points = [tuple(map(int, input().split())) for _ in range(N)]

result = 0

for K in K_list:
    hashmap = {}
    for x, y in points:
        key = y - K * x
        if key in hashmap:
            hashmap[key] += 1
        else:
            hashmap[key] = 1
    for count in hashmap.values():
        if count >= 2:
            result += count * (count - 1)
print(result)

4. 백준 32337 제비통신 파이썬(Python) 정답 코드 해설

 

1. 입력 처리:
   • N, M을 입력받고, K_list에 M개의 기울기를 저장한다.
   • 각 좌표를 points 리스트에 저장한다.
2. 기울기별로 처리:
   • for K in K_list:를 통해 각 기울기에 대해 반복한다.
   • 각 기울기에 대해 새로운 hashmap을 생성한다.
3. 좌표 변환 및 해시맵 구축:
   • 각 점 (x,y)에 대해 key = y - K * x를 계산한다.
   • 이 key를 이용하여 동일한 직선 위에 있는 점들의 개수를 센다.
4. 쌍의 수 계산 및 합산:
   • hashmap의 각 값에 대해, 점의 개수가 2개 이상이면 count * (count - 1)을 결과에 더한다.
   • 이는 순서를 고려한 한양이와 세종이의 모든 경우의 수다.
5. 결과 출력:
   • 모든 기울기에 대해 계산된 result를 출력한다.

이렇게 구현하면 시간 복잡도는 O(M×N)이며, N과 M의 최대 값이 각각 50,000과 10이므로 충분히 빠르게 동작한다. 또한, 좌표와 기울기가 정수이므로 부동소수점 오차 없이 정확한 계산이 가능하다.

5. 백준 32337 제비통신 제출 결과

백준 32337 제비통신 제출결과

 

도움이 되셨다면 공감과 댓글 부탁드립니다.