[CodeTree] 예술성 - 삼성 SW 역량테스트 2022 상반기 오전 2번 문제

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

 

문제 분석

• NxN 크기의 격자에 1 ~ 10까지의 색상을 숫자로 표현한 후 예술성을 평가하는 알고리즘을 적용하고자 함.
• 그룹 탐색
  • 동일한 숫자가 상하좌우로 인접해있는 경우 동일한 그룹이라고 가정.
  • 동일한 숫자이지만 상하좌우로 인접해있지 않은 그룹은 서로 다른 그룹으로 가정.
  • NxN 격자 내 존재하는 모든 그룹을 탐색.
• 예술 점수 계산
  • 예술 점수는 모든 그룹 쌍의 조화로움의 합으로 정의.
  • 예시로, 그룹 A와 그룹 B의 조화로움을 측정한다고 하면, (그룹 A의 칸 수 + 그룹 B의 칸 수) * 그룹 A의 값 * 그룹 B의 값 * 두 그룹이 맞닿아 있는 변의 수로 정의됨.
• 회전
  • 정중앙을 기준으로 십자가 모양은 시계 방향으로 회전.
  • 십자가를 기준으로 좌상단, 우상단, 좌하단, 우하단의 분할 된 영역은 각각 반시계 방향으로 회전.
• 초기 예술 점수, 1회전 후 예술 점수, 2회전 후 예술 점수, 3회전 후 예술 점수의 합을 Return하는 문제.

 

문제 접근

• 초기화 단계
  • NxN 격자와 상하좌우 이동을 위한 배열 선언.
  • 회전 후 예술 점수 계산이 아닌 예술 점수 계산 후 회전이기 때문에, 총 4회의 예술 점수를 구하는 과정이 필요함.
• 그룹 탐색
  • (0, 0) -> (N-1, N-1)까지 순차적으로 탐색하며, 방문하지 않은 좌표에 대해 BFS 알고리즘을 활용하여 그룹 탐색 과정을 수행함.
  • 같은 값이지만 다른 그룹임을 구분하기 위해, 우선적으로 탐색한 그룹부터 1, ... 순서대로 그룹 번호를 부여함.
  • 그룹 내 좌표 간 순서는 따로 필요없으니, set() 자료구조를 활용하여 저장.
• 예술 점수 계산
  • 그룹 간 예술 점수를 모두 계산하고, 이를 누적합 한 결과를 최종 Return해야 함.
  • 총 탐색 된 그룹의 수를 K라고 할 때, (1, 2), (1, 3), ....(K-2, K-1)까지 Combination 형태로 그룹 간 예술 점수를 구함.
  • 두 그룹을 비교할 때, 한 그룹을 기준으로 상하좌우 탐색하고, 다른 그룹에 속하는지 판단함으로써 인접한 블록 수 계산 과정을 수행.
• 회전
  • 정중앙의 십자가 모양을 기준으로 분할 된 배열들을 반시계 방향으로 90도를 회전하는 rotate_right_90() 함수 선언하고, 값을 update해주는 rotate_sub_arr() 함수 선언.
  • 정중앙의 십자가 모양을 시계 방향으로 회전하는 rotate_center() 함수 선언.
• 누적된 예술 점수를 Return하여 종료.

 

소스 코드

# define lib
from collections import deque

# set value from input
n = int(input())
field = [list(map(int, input().split())) for _ in range(n)]
direc = [(-1, 0), (0, 1), (1, 0), (0, -1)]

# define function
def rotate_right_90(arr):
    return [list(matrix)[::-1] for matrix in zip(*arr)]

def rotate_sub_arr(arr, r1, r2, c1, c2):
    new_arr = rotate_right_90([tmp[c1:c2] for tmp in arr[r1:r2]])
    for i in range(r1, r2):
        for j in range(c1, c2):
            arr[i][j] = new_arr[i-r1][j-c1]

def rotate_center(arr):
    u_to_d, r_to_l = [], []
    for i in range(n):
        u_to_d.append(arr[i][n//2])
        r_to_l.append(arr[n//2][n-i-1])
    
    for i in range(n):
        arr[i][n//2] = r_to_l[i]
        arr[n//2][i] = u_to_d[i]

# run
time, score = 0, 0
while time < 4:
    # find groups
    group, group_idx, group_value = dict(), 1, dict()
    visit = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if visit[i][j]:
                continue
            
            visit[i][j] = True
            dq, cur_group = deque([(i, j)]), {(i, j)}
            while dq:
                cx, cy = dq.popleft()
                for dx, dy in direc:
                    nx, ny = cx+dx, cy+dy
                    if nx < 0 or nx >= n or ny < 0 or ny >= n or field[nx][ny] != field[i][j] or visit[nx][ny]:
                        continue
                    visit[nx][ny] = True
                    dq.append((nx, ny))
                    cur_group.add((nx, ny))
            
            group[group_idx] = cur_group
            group_value[group_idx] = field[i][j]
            group_idx += 1
    
    # calculate score
    for i in range(1, group_idx):
        for j in range(i+1, group_idx):
            if i == j:
                continue
            tmp_score = 0
            for tx, ty in group[i]:
                for dx, dy in direc:
                    nx, ny = tx+dx, ty+dy
                    if (nx, ny) in group[j]:
                        tmp_score += 1
            score += (len(group[i]) + len(group[j])) * group_value[i] * group_value[j] * tmp_score
            
    if time < 3:
        rotate_sub_arr(field, 0, n//2, 0, n//2)
        rotate_sub_arr(field, 0, n//2, n//2+1, n)
        rotate_sub_arr(field, n//2+1, n, 0, n//2)
        rotate_sub_arr(field, n//2+1, n, n//2+1, n)
        rotate_center(field)
        time += 1
    else:
        break

print(score)

• 제출 횟수: 1회
• 풀이 시간: 40분