[코드트리/삼성SW역량테스트] 예술성 (Python)

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

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

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:24:43

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

그래프 회전을 유의하면 되겠다.(시계방향, 반시계방향, 각 사각형의 기준 좌표 맞추기) 이외에는 평범한 문제(물론 2차원 리스트 구현이 익숙하다는 전제 하에서...!)

 

 

풀이 코드

import sys
input = sys.stdin.readline

dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]

N = int(input())
maps = [list(map(int, input().split())) for _ in range(N)]
ans = 0

def search() :
    global group, visited
    visited = [[False]*N for _ in range(N)]
    group = list()
    for i in range(N) :
        for j in range(N) :
            if not visited[i][j] :
                dfs(i, j)

def dfs(r, c) :
    target = maps[r][c]
    visited[r][c] = True
    _group = [target, (r, c)]
    q = [(r, c)]
    while q :
        r, c = q.pop()
        for i in range(4) :
            ar, ac = r + dr[i], c + dc[i]
            if -1 < ar < N and -1 < ac < N and not visited[ar][ac] and maps[ar][ac] == target :
                visited[ar][ac] = True
                _group.append((ar, ac))
                q.append((ar, ac))
    group.append(_group)


def compare() :
    global ans
    for i in range(len(group) - 1) :
        group_1 = group[i]
        for j in range(i+1, len(group)) :
            group_2 = group[j]
            score = (len(group_1) + len(group_2) - 2) * group_1[0] * group_2[0]
            cnt = 0
            for r1, c1 in group_1[1:] :
                for r2, c2 in group_2[1:] :
                    if abs(r1 - r2) + abs(c1 - c2) == 1 :
                        cnt += 1
            score *= cnt
            ans += score

def rotate_cross() :
    new_rotate = [[0]*N for _ in range(N)]
    for i in range(N) :
        for r, c in [(i, N//2), (N//2, i)] :
            new_rotate[N-c-1][r] = maps[r][c]
    for i in range(N) :
        for r, c in [(i, N//2), (N//2, i)] :
            maps[r][c] = new_rotate[r][c]

def rotate_square(r, c) :
    new_rotate = [[0]*(N // 2) for _ in range(N // 2)]
    for i in range(N // 2) :
        for j in range(N // 2) :
            new_rotate[j][N//2-i-1] = maps[r+i][c+j]
    for i in range(N // 2) :
        for j in range(N // 2) :
            maps[r+i][c+j] = new_rotate[i][j]

def rotate() :
    rotate_cross()
    for i in [0, N//2+1] :
        for j in [0, N//2+1] :
            rotate_square(i, j)

for _ in range(4) :
    search()
    compare()
    rotate()
print(ans)

풀이 완료!