[코드트리] 예술성 (python 정답 코드)

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

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

 

 

90도 회전하는 원리를 아직도 헷갈려한다.. 큰일이다..

예술성 구하는 로직은 30분도 안 걸렸는데 회전 로직만 2시간 넘게 걸렸다...

 

from collections import deque
import collections

n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]

# 상하좌우로 인접해있는 경우 동일한 그룹
# (그룹 a 칸의 수 + 그룹 b 칸의 수) x 그룹 a 숫자 x 그룹 b 숫자 x 서로 맞닿아 있는 변의 수로
# 초기 예술 점수 + 1회전 이후 예술 점수 + 2회전 이후 예술 점수 + 그리고 3회전 이후 예술 점수

di = [0, 1, 0, -1]
dj = [1, 0, -1, 0]

def bfs(si, sj):
    group = [(si, sj)]
    dq = deque([(si, sj)])
    visited[si][sj] = True

    while dq:
        ci, cj = dq.popleft()

        for d in range(4):
            ni = ci + di[d]
            nj = cj + dj[d]

            if 0 <= ni < n and 0 <= nj < n and not visited[ni][nj]:
                if board[ni][nj] == board[ci][cj]:
                    visited[ni][nj] = True
                    group.append((ni, nj))
                    dq.append((ni, nj))

    return group

answer = 0

for t in range(4):
    groups = []
    visited = [[False] * n for _ in range(n)]
    # 그룹 만들기
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                groups.append(bfs(i, j))

    # 조화로움 구하기
    for i in range(len(groups)):
        for j in range(i+1, len(groups)):
            count = 0

            for gi, gj in groups[i]:
                for d in range(4):
                    ni = gi + di[d]
                    nj = gj + dj[d]

                    if 0 <= ni < n and 0 <= nj < n and (ni, nj) in groups[j]:
                        if board[ni][nj] != board[gi][gj]:
                            count += 1
                    
            
            a = board[groups[i][0][0]][groups[i][0][1]]
            b = board[groups[j][0][0]][groups[j][0][1]]
            answer += (len(groups[i]) + len(groups[j])) * a * b * count

    if t == 3:
        break

    # 회전 시키기
    # 십자가 회전
    new_board = [[0] * n for _ in range(n)]
    garo = board[n//2]
    sero = [board[i][n//2] for i in range(n)]
    
    for i in range(n):
        new_board[i][n//2] = garo[::-1][i]
        new_board[n//2][i] = sero[i]


    # 사각형 회전
    for i in range(n//2):
        for j in range(n//2):
            new_board[i][n//2-j-1] = board[j][i]

    for i in range(n//2):
        for j in range(n//2):
            new_board[i][n//2+1+n//2-j-1] = board[j][n//2+1+i]

    for i in range(n//2):
        for j in range(n//2):
            new_board[n//2+1+i][n//2-j-1] = board[n//2+1+j][i]

    for i in range(n//2):
        for j in range(n//2):
            new_board[n//2+1+i][n//2+1+n//2-j-1] = board[n//2+1+j][n//2+1+i]

    board = new_board
    
print(answer)