(Python) - BOJ(3042번) : 트리플렛

https://www.acmicpc.net/problem/3042

3042번: 트리플렛

---

• 해설 : 

상근이와 창영이는 트리플렛이라는 게임을 하고 있다. 이 게임을 하려면 칠판에 N*N 그리드를 그려야 한다. 그 다음 알파벳 대문자를 적절히 각 칸에 써 넣는다. 한 알파벳을 여러 칸에 쓸 수는 없다.

 

여기까지는 게임을 하기 위해 준비하는 과정이다. 트리플렛의 목표는 직선을 이루는 세 글자를 되도록 많이 찾는 것이다. 세 글자가 직선을 이루려면, 글자가 있는 칸의 중심을 연결한 선이 선분이어야 한다.

 

칠판에 그린 그리드의 상태가 주어졌을 때, 직선을 이루는 세 글자(트리플렛)의 개수를 찾는 프로그램을 작성하시오.

 

 

 

---

• 풀이 :

ccw 개념을 사용하면 된다. 이는 어떤 점 3개가 일직선위에 있는지 찾는 방법이다. 

 

 

 

---

• 소스코드 : 

 

import sys
from itertools import combinations
input = sys.stdin.readline
 
def ccw(p1, p2, p3):
    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3
    return (x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3)
 
if __name__ == "__main__":
    N = int(input())
    maps = [list(input()) for _ in range(N)]
    ans = []
    for i in range(N):
        for j in range(N):
            if maps[i][j] != '.':
                ans.append([i,j])
    cnt = 0
    for value in combinations(ans,3):
        if ccw(value[0],value[1],value[2]) == 0:
            cnt +=1
    print(cnt)