코딩 테스트(Python) 교점에 별 만들기

문제 설명

Ax + By + C = 0으로 표현할 수 있는 n개의 직선이 주어질 때, 이 직선의 교점 중 정수 좌표에 별을 그리려 합니다.

예를 들어, 다음과 같은 직선 5개를

• 2x - y + 4 = 0
• 2x - y + 4 = 0
• y + 1 = 0
• 5x - 8y - 12 = 0
• 5x + 8y + 12 = 0

좌표 평면 위에 그리면 아래 그림과 같습니다.

이때, 모든 교점의 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4), (1.5, 1.0), (2.1, -0.19), (0, -1.5), (-2.1, -0.19), (-1.5, 1.0)입니다. 이 중 정수로만 표현되는 좌표는 (4, 1), (4, -4), (-4, -4), (-4, 1), (0, 4)입니다.

만약 정수로 표현되는 교점에 별을 그리면 다음과 같습니다.

 

이때 격자판은 무한히 넓으니 모든 별을 포함하는 최소한의 크기만 나타내면 됩니다.

직선 A, B, C에 대한 정보가 담긴 배열 line이 매개변수로 주어집니다. 이때 모든 별을 포함하는 최소 사각형을 return 하도록 solution 함수를 완성해주세요.

 

from collections import deque

def solution(line):
    # 입력된 직선 방정식 리스트를 deque로 변환하여 사용 (y=1 형태로 정리)
    line = deque(line) 
    cross = []  # 교차점 저장 리스트

    # 교차점 찾기
    while line :
        first = line.popleft()  # 첫 번째 직선
        for i in line :  # 나머지 직선들과 비교
            # 두 직선이 평행하지 않다면 교차점 계산
            if (first[0]*i[1]-first[1]*i[0]) != 0 :
                # 교차점의 x, y 좌표 계산
                cross.append([(first[1]*i[2]-first[2]*i[1])/(first[0]*i[1]-first[1]*i[0]) ,
                             (first[2]*i[0]-first[0]*i[2])/(first[0]*i[1]-first[1]*i[0])])
            else :
                continue  # 평행한 직선은 건너뜀

    result = []  # 교차점 좌표 저장 리스트
    x, y = [], []  # x, y 좌표별로 각각 저장

    # 교차점이 없으면 "."만 있는 리스트 반환
    if not cross:
        return ["."]
    
    # 유효한 교차점만 추려서 저장 (정수 좌표만)
    for i, j in cross :
        if i.is_integer() and j.is_integer() :
            result.append([int(i), int(j)])  # 정수 좌표로 변환
            x.append(int(i))
            y.append(int(j))
    
    # 교차점의 x, y 범위 구하기
    min_x_cross, max_x_cross, min_y_cross, max_y_cross = min(x), max(x), min(y), max(y)

    # 결과 좌표를 0,0 기준으로 이동 (최소 x, y 값을 빼기)
    for i in range(len(result)):
        result[i][0] -= min_x_cross
        result[i][1] -= min_y_cross

    # x, y 크기 구하기
    max_x = max_x_cross - min_x_cross
    max_y = max_y_cross - min_y_cross

    # 최종 결과가 될 2D 맵 초기화
    answer = [["." for i in range(max_x + 1)] for j in range(max_y + 1)]

    # 교차점 좌표에 '*' 표시
    for i, j in result:
        answer[max_y - j][i] = '*'  # y좌표는 반전시켜서 그려야 하기 때문

    # 결과 맵을 문자열로 변환
    answer = [''.join(row) for row in answer]

    return answer  # 결과 반환