[Python][SWEA] 10580. 전봇대 D3

🗒️ 파이썬 코드 풀이

from itertools import combinations

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    lst = [list(map(int,input().split())) for _ in range(N)]

    connection = 0
    combi = list(combinations(lst,2))
    for c in combi:
        if c[0][0] > c[1][0] and c[0][1] < c[1][1] : connection += 1
        elif c[0][0] < c[1][0] and c[0][1] > c[1][1] : connection += 1

    print(f"#{tc} {connection}")

 

1. (a1,b1) 과 (a2,b2) 이렇게 전선의 위치가 있을때 a1<a2 and b1<b2 이런식으로 a2,b2의 좌표가 모두 커야 전선 연결지점이 안생긴다.  

 

2. itertools를 사용해서, 할 수 있는 모든 조합을 생성하고, a1과 a2 / b1과 b2를 각각 비교해준다

 

3. a2,b2 좌표 중 한 쪽이라도 1의 좌표보다 작으면 전선이 겹치므로 +1을 해준다.

 

🧐 문제 코멘트

어려운 문제인 줄 알았는데, 전선이 언제 겹치는지만 알면 쉽게 풀 수 있는 문제이다.

itertools를 쓰는거는 좀 얍삽해보일 수도 있지만... 그래도 swea 환경에서는 큰 문제가 없다 !

 

# 조합 예시
N = 4
lst = [10, 9, 8, 7]

for i in range(N-1) :
    for j in range(i+1,N) :
        print(lst[i],lst[j])

itertools를 사용 할 수 없는 환경이면, 해당 코드 방식으로 조합을 생성시킬 수 있다.

i ->  0 ~ N-1     //   j  ->  i+1 ~ N

---

📚 문제

현우는 길을 가다가 전선들이 복잡하게 꼬여 있는 전봇대 두 개를 보았다. 두 전봇대는 높이가 매우 높으며, N개의 팽팽한 전선으로 연결되어 있었다. 두 전선이 끝점이 같은 경우는 없으나, 교차하는 경우는 있다. 이를 그림으로 하면 아래와 같다. (전선 3개가 있으며, 교차점 2개가 검은색으로 칠해졌다.)

 

세 개 이상의 전선이 하나의 점에서 만나지 않는다고 가정하자. 이 전봇대에는 총 몇 개의 교차점이 있을까?

 

 

[입력]

첫 번째 줄에 테스트 케이스의 수 TC가 주어진다. 이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 주어지는 전선의 개수 N이 주어진다 (1 ≤ N ≤1000).

이후 N개의 줄에 두 양의 정수 Ai, Bi 가 주어진다. (1 ≤ Ai, Bi ≤ 10000)이는 i번째 전선이, 첫번째 전봇대의 Ai cm 고도에 걸려 있고, 두 번째 전봇대의 Bi cm 고도에 걸려 있음을 뜻한다.

모든 Ai는 서로 다르고, 모든 Bi 도 서로 다르다. (두 전선의 끝점이 같은 경우가 없기 때문이다.) 세 전선이 한 점에서 만나지 않게 입력이 주어진다.

 

[출력]
각 테스트 케이스마다 한 줄씩 교차점의 개수를 출력하라.