[백준] 평행선(python)

백준, 평행선

2358번: 평행선

TL;DR

• 해시(Hash)

문제 요약

1. 평면 상에 주어진 n개의 점 중 서로 다른 두 점을 선택해서 만들 수 있는 x축 또는 y축에 평행한 직선이 몇 개나 있는지 출력하라.

 

- 평면 상에 존재하는 점들로 만들 수 있는 x축 또는 y축에 평행한 직선의 수를 구하는 문제이다.

- 문제 상에 숨겨져 있는 뜻이 있는데 다음과 같은 경우이다.

   - (1, 2), (1, 3), (1, 4)와 같이 입력이 주어졌을 때, 만들 수 있는 직선의 수는 총 3C2인 3개이다.

   - 하지만 이는 모두 y축에 평행한 직선으로 모두 같은 직선으로 취급해야 한다.

   - 따라서, 이 경우 답은 1이 된다.

입출력 형태

입출력 예시

 

예시 1 :: x축에 평행한 직선 2개((0, 0) - (10, 0), (0, 10) - (10, 10)), y축에 평행한 직선 2개((0, 0) - (0, 10), (10, 0) - (10, 10)) 총 4가지가 존재한다.

풀이

x축과 y축으로 평행한 직선이 되기 위해서는 x좌표 또는 y좌표가 일치한 상태에서 다른 값이 다른 값이 되어야 한다. 따라서 x좌표를 key로 한 딕셔너리, y좌표를 key로 한 딕셔너리를 작성하여 key에 속하는 value들을 따져서 문제를 해결할 수 있다.

import sys
from collections import defaultdict
INPUT = sys.stdin.readline

N = int(INPUT())
x_dicts = defaultdict(list)
y_dicts = defaultdict(list)
answer = 0
for _ in range(N):
  a, b = map(int, INPUT().split())
  x_dicts[a].append(b)
  y_dicts[b].append(a)

for key in x_dicts:
  if len(x_dicts[key]) >= 2:
    answer += 1
for key in y_dicts:
  if len(y_dicts[key]) >= 2:
    answer += 1
print(answer)

 

이를 위해서 x좌표를 key로 하는 x_dicts와 y좌표를 key로 하는 y_dicts를 생성하였다.

key에 속하는 value가 1개만 있을 경우는 서로 다른 두 점이 아니므로 평행선이 되지 않는다. 1개를 초과한 경우에는 동일한 평행한 직선 내에 속한다는 의미로 해석할 수 있다. 따라서 key에 속해있는 value들의 길이가 1을 초과할 경우 정답을 1 추가하는 방식으로 구현하였다.