[CodeTree] 고대 문명 유적 탐사 - 삼성 SW 역량테스트 2024 상반기 오전 1번 문제

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

 

문제 분석

• 5x5 격자 내 다양한 유물 조각이 배치되어 있으며, 유물 조각은 1 ~ 7까지 7가지가 존재함.
• 탐사 진행
  • 5x5 격자 내에서 3x3 격자를 선택하여 회전할 수 있음.
  • 회전 방향은 90도, 180도, 270도가 존재하며 세 회전 각도 중 하나로 무조건 회전해야 함.
  • 가능한 회전 방법은 (유물 1차 가치를 최대로 획득하는 순서, 회전 각도가 낮은 순서, 중심 c가 낮은 , 중심 r이 낮은 구간을 선택하여 정해진 각도만큼 회전을 진행함.
• 유물 획득
  • 5x5 격자 내에서 상하좌우로 3개 이상 연결된 유물 조각이 있을 경우, 하나의 큰 조각이 되어 사라지게 됨.
  • 없어진 유물 조각 영역에는 새로운 조각이 채워지는데, 영역을 채울 때 (c가 낮은, r이 큰) 순서대로 벽면에 써있는 숫자를 채워 나감.
  • 1차 유물 획득이 불가능한 case의 경우, 더 이상 게임을 수행하지 않고 종료함.
• 유뮬 연쇄 획득
  • 1차 유물 획득 -> 벽면 숫자 채우기가 끝난 이후에, 5x5 격자 위 3개 이상의 큰 조각이 존재한다면 연쇄적으로 수행함.
• 각 턴에  얻은 유물 조각의 합을 출력하는 문제

 

소스 코드

# define lib
from copy import deepcopy
from collections import deque

# set value from input
N = 5
K, M = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(N)]
items = deque(list(map(int, input().split())))
windows = [(i, j) for i in range(3) for j in range(3)]
direc = [(-1, 0), (0, 1), (1, 0), (0, -1)]

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

# run
time, exit_flag = 0, True
while exit_flag and time < K:
    # find prior 3x3 window
    _candits, turn_score = [], 0
    for sx, sy in windows:
        new_field = deepcopy(field)
        for rot_idx in range(3):
            # rotate_90 (total 270)
            sub_arr = rotate_90([tmp[sy: sy+3] for tmp in new_field[sx: sx+3]])
            for i in range(sx, sx+3):
                for j in range(sy, sy+3):
                    new_field[i][j] = sub_arr[i-sx][j-sy]
            
            # get first score
            total_groups = []
            visit = [[False]*N for _ in range(N)]
            for i in range(N):
                for j in range(N):
                    if visit[i][j]:
                        continue                   
                    groups, dq = [(i, j)], deque([(i, j)])
                    visit[i][j] = True

                    while dq:
                        cx, cy = dq.popleft()
                        for dx, dy in direc:
                            nx, ny = cx+dx, cy+dy
                            if 0 <= nx < N and 0 <= ny < N and new_field[i][j] == new_field[nx][ny]:
                                if not visit[nx][ny]:
                                    visit[nx][ny] = True
                                    groups.append((nx, ny))
                                    dq.append((nx, ny))
                    if len(groups) <= 2:
                        continue
                    total_groups.extend(groups)
            
            # add candidate
            _candits.append((total_groups, rot_idx, sy+1, sx+1)) # group_pos, rot_idx, c, r

    # get prior
    _candits.sort(key=lambda x: (-len(x[0]), x[1], x[2], x[3])) # max_len, min_rot, min_c, min_r
    groups, rot_idx, gy, gx = _candits[0]
    groups.sort(key=lambda x: (x[1], -x[0])) # min_c, max_r
    turn_score += len(groups)

    # rotate field
    for _ in range(rot_idx+1):
        sub_arr = rotate_90([tmp[gy-1:gy+2] for tmp in field[gx-1:gx+2]])
        for i in range(gx-1, gx+2):
            for j in range(gy-1, gy+2):
                field[i][j] = sub_arr[i-gx+1][j-gy+1]
    
    # update values
    for gx, gy in groups:
        field[gx][gy] = items.popleft()
    
    # check cascade
    while True:
        total_groups = []
        visit = [[False]*N for _ in range(N)]
        for i in range(N):
            for j in range(N):
                if visit[i][j]:
                    continue                   
                groups, dq = [(i, j)], deque([(i, j)])
                visit[i][j] = True

                while dq:
                    cx, cy = dq.popleft()
                    for dx, dy in direc:
                        nx, ny = cx+dx, cy+dy
                        if 0 <= nx < N and 0 <= ny < N and field[i][j] == field[nx][ny]:
                            if not visit[nx][ny]:
                                visit[nx][ny] = True
                                groups.append((nx, ny))
                                dq.append((nx, ny))
                if len(groups) <= 2:
                    continue
                total_groups.extend(groups)
        
        if len(total_groups) == 0:
            break
        
        total_groups.sort(key=lambda x: (x[1], -x[0])) # min_c, max_r
        turn_score += len(total_groups)
        for tx, ty in total_groups:
            field[tx][ty] = items.popleft()

    if turn_score == 0:
        break
    print(turn_score, end=" ")
    time += 1

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