[Samsung] 2022-1 오전 2번 예술성

[Samsung] 2022-1 오전 2번 예술성

Question

Language: Python

Difficulty: Gold 3

해당 문제는 주어진 문제의 시뮬레이션을 구현하는 문제이며 bfs가 활용된다.

시뮬레이션 과정은 아래와 같다.

1. 예술성 점수 구하기
2. 배열의 회전

구체적인 과정을 살펴보자

1. 예술성 점수 구하기

예술성 점수를 구하는 과정은 크게 3과정이다.

우선, bfs을 활용하여 각각의 component을 찾아주는 작업을 진행한다. 추가적으로 각각의 좌표가 해당하는 그룹 인덱스를 저장하는 group_map도 생성해서 반환한다.

def get_components():
    #각 좌표에 대해 각각 어느 그룹에 속하는지를 나타내는 배열
    group_map=[[0]*n for _ in range(n)]

    #각각의 집합들을 찾는 부분
    visited=[[False] * n for _ in range(n)]
    #각각의 그룹들을 저장하는 배열
    components=[]

    group_index=0
    for start_row in range(n):
        for start_col in range(n):
            #방문 여부
            if visited[start_row][start_col]:
                continue
            queue=deque([(start_row,start_col)])
            
            group_value=board[start_row][start_col]
            component=[group_value]
            
            while queue:
                row,col=queue.popleft()

                if visited[row][col]:
                    continue
                
                visited[row][col]=True
                component.append((row,col))
                group_map[row][col]=group_index
                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    #범위를 벗어나는 경우
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        continue
                    
                    if board[next_row][next_col] == group_value:
                        queue.append((next_row,next_col))
                    
            components.append(component)
            group_index+=1
    return group_map,components

그런 다음, 각 그룹 간 인접한 변의 갯수를 구하기 위해 각 그룹 내에 있는 좌표들에 대해 인접 좌표를 조사해서 현재 그룹과 인접한 좌표가 속해있는 그룹에 대한 adjacent_counts 배열 값을 갱신한다.

이 과정을 통해 모든 (team_a,team_b)에 대한 team_a <-> team_b 간에 인접한 변의 갯수를 저장하게 된다. 한번에 일괄적으로 저장하므로써 이후, combination 작업에서 불필요한 중복 탐색을 줄일 수 있다.

def get_adjacent_counts(group_map,components,group_length):
    adjacent_counts=[[0] * group_length for _ in range(group_length)]

    for index in range(group_length):
        component=components[index]
        for row,col in component[1:]:
            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #범위를 벗어나는 경우
                if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                    continue
                
                #해당 그룹과 다른 그룹에 대한 인접 변의 갯수를 증가시킨다.
                adjacent_counts[index][group_map[next_row][next_col]]+=1

    return adjacent_counts

마지막으로, 모든 그룹의 조합에 대해 예술성 점수를 구한다

harmony_points=0
#a,b 조합에 대하여 조화로움 점수를 구하는 작업을 진행한다.
for combination in combinations(range(group_length),2):
    group_a_index,group_b_index=combination
    group_a_value=components[group_a_index][0]
    group_b_value=components[group_b_index][0]
    adjacent_count=adjacent_counts[group_a_index][group_b_index]
    point=(len(components[group_a_index][1:])+len(components[group_b_index][1:])) * group_a_value * group_b_value * adjacent_count
    harmony_points+=point
return harmony_points

1. 배열 회전하기

배열 회전은 크게 2가지 과정으로 각 4개의 귀퉁이에 있는 정사각형에 대한 회전과 중앙에 위치한 십자가의 회전이 동반된다.

정사각형의 회전은 아래의 함수와 같이 구현한다. 배열의 회전 과정에서 시작 좌표에 대한 평행이동을 적용하여 회전 이후 기존의 위치에 저장될 수 있도록 구현하여 회전 간 독립성을 유지가 가능하다.

def rotate_quarter(new_board,start_row,start_col,end_row,end_col):
    for row in range(start_row,start_row+n//2):
        for col in range(start_col,start_col+n//2):
            new_board[start_row+col-start_col][start_col+end_row-row]=board[row][col]

#좌상단
rotate_quarter(new_board,0,0,n//2-1,n//2-1)
#우상단
rotate_quarter(new_board,0,n//2+1,n//2-1,n-1)
#좌하단
rotate_quarter(new_board,n//2+1,0,n-1,n//2-1)
#우하단
rotate_quarter(new_board,n//2+1,n//2+1,n-1,n-1)

십자가를 구하는 부분은 아래와 같다

#십자가의 수평선
for col in range(n):
    new_board[n//2][col]=board[col][n//2]

#십자가의 수직선
for row in range(n):
    new_board[row][n//2]=board[n//2][n-row-1]

Solution

from collections import deque
from itertools import combinations

def get_components():
    #각 좌표에 대해 각각 어느 그룹에 속하는지를 나타내는 배열
    group_map=[[0]*n for _ in range(n)]

    #각각의 집합들을 찾는 부분
    visited=[[False] * n for _ in range(n)]
    #각각의 그룹들을 저장하는 배열
    components=[]

    group_index=0
    for start_row in range(n):
        for start_col in range(n):
            #방문 여부
            if visited[start_row][start_col]:
                continue
            queue=deque([(start_row,start_col)])
            
            group_value=board[start_row][start_col]
            component=[group_value]
            
            while queue:
                row,col=queue.popleft()

                if visited[row][col]:
                    continue
                
                visited[row][col]=True
                component.append((row,col))
                group_map[row][col]=group_index
                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    #범위를 벗어나는 경우
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        continue
                    
                    if board[next_row][next_col] == group_value:
                        queue.append((next_row,next_col))
                    
            components.append(component)
            group_index+=1
    return group_map,components

def get_adjacent_counts(group_map,components,group_length):
    adjacent_counts=[[0] * group_length for _ in range(group_length)]

    for index in range(group_length):
        component=components[index]
        for row,col in component[1:]:
            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #범위를 벗어나는 경우
                if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                    continue
                
                #해당 그룹과 다른 그룹에 대한 인접 변의 갯수를 증가시킨다.
                adjacent_counts[index][group_map[next_row][next_col]]+=1

    return adjacent_counts


def get_score():    
    group_map,components=get_components()
    group_length=len(components)
    adjacent_counts=get_adjacent_counts(group_map,components,group_length)
    harmony_points=0
    #a,b 조합에 대하여 조화로움 점수를 구하는 작업을 진행한다.
    for combination in combinations(range(group_length),2):
        group_a_index,group_b_index=combination
        group_a_value=components[group_a_index][0]
        group_b_value=components[group_b_index][0]
        adjacent_count=adjacent_counts[group_a_index][group_b_index]
        point=(len(components[group_a_index][1:])+len(components[group_b_index][1:])) * group_a_value * group_b_value * adjacent_count
        harmony_points+=point
    return harmony_points

def rotate_quarter(new_board,start_row,start_col,end_row,end_col):
    for row in range(start_row,start_row+n//2):
        for col in range(start_col,start_col+n//2):
            new_board[start_row+col-start_col][start_col+end_row-row]=board[row][col]

    
def rotate():
    new_board=[[0] * n for _ in range(n)]

    #좌상단
    rotate_quarter(new_board,0,0,n//2-1,n//2-1)
    #우상단
    rotate_quarter(new_board,0,n//2+1,n//2-1,n-1)
    #좌하단
    rotate_quarter(new_board,n//2+1,0,n-1,n//2-1)
    #우하단
    rotate_quarter(new_board,n//2+1,n//2+1,n-1,n-1)

    #십자가의 수평선
    for col in range(n):
        new_board[n//2][col]=board[col][n//2]

    #십자가의 수직선
    for row in range(n):
        new_board[row][n//2]=board[n//2][n-row-1]
    
    #회전을 기존 맵에 반영
    for row in range(n):
        for col in range(n):
            board[row][col]=new_board[row][col]

def print_board(title,board):
    print(title)
    for row in board:
        print(*row)   


def solution():
    total_points=0
    for _ in range(4):
        total_points+=get_score()
        rotate()

    print(total_points)

if __name__ == "__main__":
    n=int(input())
    board=[list(map(int,input().split())) for _ in range(n)]
    dy=[-1,0,1,0]
    dx=[0,1,0,-1]
    solution()