[코드트리] 파이썬 - 예술성

https://www.codetree.ai/training-field/frequent-problems/artistry/description?page=3&pageSize=20&username=

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

 

코드트리 삼성 sw 역량 기출문제

# 조건

• N x N 크기의 격자에서 각 칸의 색깔을 1이상 10이하의 숫자로 표현한다.
• 동일한 숫자가 상하좌우로 인접해있는 경우 동일한 그룹이라 본다.
• 예술 점수는 모든 그룹 쌍의 조화로움의 합으로 정의
  • 그룹 a와 그룹 b의 조화 로움은
  • (그룹 a에 속한 칸의 수 + 그룹 b에 속한 칸의 수 ) x 그룹 a를 이루고 있는 숫자 값 x 그룹 b를 이루고 있는 숫자 값 x 그룹 a와 그룹 b가 서로 맞닿아 있는 변의 수
  • 그룹 쌍 간의 조화로움 값이 0보다 큰 조합인 (G1, G2), (G2, G3), (G2, G4), (G3, G4) 의 조화로움 값을 전부 더하면 48 + 192 + 152 + 156 = 548 이 되고 초기 예술 점수라고 부른다.
• 초기 예술 점수를 구한 뒤에는 회전을 진행
• 회전은 정중을 기준으로 두 선을 그어 만들어지는 십자가 모양과 그 외 부분으로 나뉘어 진행
  • 십자 모양은 통째로 반시계 방향으로 90도 회전
  • 십자 모양 제외한 4개의 정사각형은 개별적으로 시계 방향으로 90도씩 회전 진행
• 이후 예술점수 구하기
• 이 때, 1회전 이후, 2회전 이후, 3회전 이후 예술 점수의 합을 구하시오.

입력

• 첫 번째 줄에 n이 주어집니다. n은 반드시 홀수입니다.
• 이후 n개의 줄에 걸쳐 각 행에 칠해져 있는 색깔에 대한 정보인 숫자들이 공백을 사이에 두고 주어집니다.
  • 3 ≤ n ≤ 29
  • 1 ≤ 주어지는 숫자 ≤ 10

# 접근 방법

• 2차원 배열 group을 통해 그룹을 분리해준다.
• group_cnt를 통해 그룹별로 개수를 세준다.
• 예술점수의 경우 다른 그룹과 겹치는 변의 개수가 중요한데 델타 함수를 사용해서 주변을 탐색해준다.
  • 번호가 다른 칸들의 좌표
  • 번호가 다른 칸들의 숫자를 구해서
  • 번호가 다른 칸들의 좌표를 활용한 그룹 번호 개수를 구해주면 된다.
• 이를 통해 구한 예술점수는 한 경우에 대해 2번 계산하므로 // 2 해주면 된다.
• 또한 회전의 경우 arr 빈 배열을 만들어서 값을 복사해준다.
  • 십자 회전의 경우 가로축과 세로축에 따라서 나눠주기
  • 사각형 회전의 경우 왼쪽 위 좌표를 0,0으로 만들어주고 공식에 따라
  • 좌표를 변경해준다.

from collections import deque  
N = int(input())  
pan = [ list(map(int, input().split())) for _ in range(N) ]  

dx, dy = [0, 0, -1, 1], [-1, 1, 0, 0]  
def group_search(x, y): # 그룹별로 번호를 매겨주는 함수.  

    visited[x][y] = True  
    q = deque([(x, y)])  

    while q:  
        px, py = q.popleft()  

        for k in range(4):  
            mx = px + dx[k]  
            my = py + dy[k]  

            if 0 <= mx < N and 0 <= my < N:  
                if pan[mx][my] == pan[px][py] and not visited[mx][my]:  
                    visited[mx][my] = True  
                    group[mx][my] = group_num  
                    group_cnt[group_num] += 1  
                    q.append((mx, my))  


def art_score(): # 예술 점수를 구해주는 함수.  

    value = 0  

    for i in range(N):  
        for j in range(N):  
            for k in range(4):  
                mx = i + dx[k]  
                my = j + dy[k]  

                if 0 <= mx < N and 0 <= my < N:  
                    if group[mx][my] != group[i][j]:  
                        g_x, g_y = group[i][j], group[mx][my] # 번호가 다른 칸들의 좌표  
                        g_x_num, g_y_num = pan[i][j], pan[mx][my] # 번호가 다른 칸들의 숫자  
                        g_x_cnt, g_y_cnt = group_cnt[g_x], group_cnt[g_y] # 번호가 다른 칸들의 좌표를 활용한 그룹 번호 개수  
                        value += (g_x_cnt + g_y_cnt) * g_x_num * g_y_num  

    return value // 2 # 한 경우에 대해 2번 계산하게 되므로 2로 나누어 줌.  


def plus_rotate(): # 십자가 모양 반시계 방향 회전  

    for i in range(N):  
        for j in range(N):  
            if i == half:  
                arr[i][j] = pan[j][i]  
            if j == half:  
                arr[i][j] = pan[N-j-1][N-i-1]  


def square_rotate(x, y, l): # 정사각형 모양 시계 방향 회전  

    for i in range(x, x+l):  
        for j in range(y, y+l):  
            ox, oy = i - x, j - y # (0, 0)으로 변환  

            rx, ry = oy, l - ox - 1 # 시계 방향 회전 공식  

            arr[rx + x][ry + y] = pan[i][j] # 모든 좌표에 적용할 수 있도록 인자(x, y)를 더해줌.  


answer = 0  
for _ in range(4):  

    group = [[0] * N for _ in range(N)] # 그룹을 분리하기 위해 만든 2차원 배열  
    group_cnt = [0] * (N * N + 1) # 그룹별로 개수를 세기위한 배열  
    group_num = 0 # 그룹 번호  
    visited = [ [False] * N for _ in range(N) ]  

    for i in range(N):  
        for j in range(N):  
            if not visited[i][j]:  
                group_num += 1  
                group[i][j] = group_num  
                group_cnt[group_num] += 1  
                group_search(i, j)  

    answer += art_score()  

    arr = [ [0] * N for _ in range(N) ] # 배열 회전하기 위해 만든 빈 배열  
    half = N // 2  

    plus_rotate()  

    square_rotate(0, 0, half)  
    square_rotate(0, half+1, half)  
    square_rotate(half+1, 0, half)  
    square_rotate(half+1, half+1, half)  

    for i in range(N):  
        for j in range(N):  
            pan[i][j] = arr[i][j]  

print(answer)