[python] 코드 트리 - 예술성

문제

https://www.codetree.ai/training-field/frequent-problems/problems/artistry

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

왼쪽 그림과 같이 배열이 주어진다면 오른쪽 그림처럼 4개의 그룹으로 만들어 질 수 있다.

 

예술 점수는 모든 그룹 쌍의 조화로움의 합으로 정의한다.

• 그룹 a와 b의 조화로움은 (그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수
• G2, G4의 조화로움은 (11 + 8) x 2 x 1 x 4 = 152가 된다.

 

 

계산이 끝나면 회전을 하는데, 가운데 십자가 부분은 왼쪽으로 90도, 십자 모양을 제외한 4개의 정사각형 영역은 오른쪽으로 90도씩 회전하면 1 라운드가 끝나게 된다.

 

n*n의 그림 정보가 주어졌을 때, 초기 예술 점수, 1회전 이후 예술 점수, 2회전 .. , 3회전 ….의 예술 점수의 합을 출력하면 된다.

 

 

풀이

문제 해결을 위해 요구되는 기술은 BFS, 배열 회전, 간단한 아이디어(?) 정도이다. 고려해야 될 부분이 많지 않아서 금방 풀어내었던 거 같다.

 

1. BFS를 사용하여 각 그룹을 구분지었다.

 

2. 각각의 group 끼리의 조화로움의 계산은 완전탐색으로 진행했다.

• group이 4개까지 있다고 하면 조화로움 계산은 다음 조합을 모두 진행함.
  • ( group 1, group 2), ( group 1, group 3), ( group 1, group 4), ( group 2, group 3), ( group 2, group 4), ( group 3, group 4)

 

3. 이후 배열 회전 부분은 십자가 부분과 4개의 영역을 각각 나눠서 회전 한 이후 하나의 배열로 통합해주었다. (아래코드 참고)

생략...

def rotate_cross(arr: List[List[int]]) -> List[List[int]]:
    """배열의 십자가 부분을 반시계 방향으로 90도 회전"""
    n = len(arr)
    new_arr = [row[:] for row in arr]  # 새로운 배열 생성
    mid = n // 2

    # 가로 줄 회전
    for i in range(n):
        new_arr[mid][i] = arr[i][mid]

    # 세로 줄 회전
    for i in range(n):
        new_arr[i][mid] = arr[mid][n-1-i]

    return new_arr

def rotate_square(arr: List[List[int]], sy: int, sx: int) -> None:
    """배열의 특정 정사각형 영역을 시계 방향으로 90도 회전"""
    n = len(arr) // 2
    temp = [[0] * n for _ in range(n)]

    # 임시 배열로 복사
    for i in range(n):
        for j in range(n):
            temp[i][j] = arr[sy+i][sx+j]

    # 시계 방향으로 90도 회전하여 원래 배열에 저장
    for i in range(n):
        for j in range(n):
            arr[sy+j][sx+n-1-i] = temp[i][j]

def rotate_all(arr: List[List[int]]) -> None:
    """전체 배열 회전: 십자가 부분 반시계 방향, 나머지 정사각형 시계 방향"""
    n = len(arr)
    # 십자가 부분 회전
    rotated_cross = rotate_cross(arr)

    # 4개의 정사각형 영역 회전
    rotate_square(arr, 0, 0)  # 좌상단
    rotate_square(arr, 0, n//2 + 1)  # 우상단
    rotate_square(arr, n//2 + 1, 0)  # 좌하단
    rotate_square(arr, n//2 + 1, n//2 + 1)  # 우하단

    # 회전된 십자가 부분을 원래 배열에 적용
    mid = n // 2
    for i in range(n):
        arr[i][mid] = rotated_cross[i][mid]
        arr[mid][i] = rotated_cross[mid][i]
        
 
 생략...

 

 

코드

import sys
from collections import deque
from typing import List, Tuple

def read_input() -> Tuple[int, List[List[int]]]:
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    return n, arr

def get_group(y: int, x: int, arr: List[List[int]], visited: List[List[bool]]) -> List[Tuple[int, int]]:
    n = len(arr)
    arr_num = arr[y][x]
    group = [(y, x)]
    queue = deque([(y, x)])
    visited[y][x] = True

    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]

    while queue:
        y, x = queue.popleft()
        for d in range(4):
            ny, nx = y + dy[d], x + dx[d]
            if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx] and arr[ny][nx] == arr_num:
                visited[ny][nx] = True
                group.append((ny, nx))
                queue.append((ny, nx))

    return group

def find_groups(arr: List[List[int]]) -> List[List[Tuple[int, int]]]:
    n = len(arr)
    visited = [[False] * n for _ in range(n)]
    return [get_group(i, j, arr, visited) for i in range(n) for j in range(n) if not visited[i][j]]

def calculate_beautiful(group_1: List[Tuple[int, int]], group_2: List[Tuple[int, int]], arr: List[List[int]]) -> int:
    n = len(arr)
    group_2_set = set(group_2)
    cnt = sum(1 for y, x in group_1 for dy, dx in [(0, 1), (1, 0), (0, -1), (-1, 0)]
              if 0 <= y + dy < n and 0 <= x + dx < n and (y + dy, x + dx) in group_2_set)
    return (len(group_1) + len(group_2)) * arr[group_1[0][0]][group_1[0][1]] * arr[group_2[0][0]][group_2[0][1]] * cnt

def rotate_cross(arr: List[List[int]]) -> List[List[int]]:
    """배열의 십자가 부분을 반시계 방향으로 90도 회전"""
    n = len(arr)
    new_arr = [row[:] for row in arr]  # 새로운 배열 생성
    mid = n // 2

    # 가로 줄 회전
    for i in range(n):
        new_arr[mid][i] = arr[i][mid]

    # 세로 줄 회전
    for i in range(n):
        new_arr[i][mid] = arr[mid][n-1-i]

    return new_arr

def rotate_square(arr: List[List[int]], sy: int, sx: int) -> None:
    """배열의 특정 정사각형 영역을 시계 방향으로 90도 회전"""
    n = len(arr) // 2
    temp = [[0] * n for _ in range(n)]

    # 임시 배열로 복사
    for i in range(n):
        for j in range(n):
            temp[i][j] = arr[sy+i][sx+j]

    # 시계 방향으로 90도 회전하여 원래 배열에 저장
    for i in range(n):
        for j in range(n):
            arr[sy+j][sx+n-1-i] = temp[i][j]

def rotate_all(arr: List[List[int]]) -> None:
    """전체 배열 회전: 십자가 부분 반시계 방향, 나머지 정사각형 시계 방향"""
    n = len(arr)
    # 십자가 부분 회전
    rotated_cross = rotate_cross(arr)

    # 4개의 정사각형 영역 회전
    rotate_square(arr, 0, 0)  # 좌상단
    rotate_square(arr, 0, n//2 + 1)  # 우상단
    rotate_square(arr, n//2 + 1, 0)  # 좌하단
    rotate_square(arr, n//2 + 1, n//2 + 1)  # 우하단

    # 회전된 십자가 부분을 원래 배열에 적용
    mid = n // 2
    for i in range(n):
        arr[i][mid] = rotated_cross[i][mid]
        arr[mid][i] = rotated_cross[mid][i]

def main():
    n, arr = read_input()
    answer = 0

    for _ in range(4):
        group_list = find_groups(arr)
        for i in range(len(group_list)):
            for j in range(i + 1, len(group_list)):
                answer += calculate_beautiful(group_list[i], group_list[j], arr)
        rotate_all(arr)

    print(answer)

if __name__ == "__main__":
    main()