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

📚 문제

https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=1&pageSize=5

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

 

말했다시피 삼성 문제는 호흡이 길기에 단계를 잘 나누어 풀자.

---

💡 풀이 과정

1. def 탐사 진행()
   1-1. ((x, y 기준 3 * 3 회전) * 3) * 9
   1-2. def 유물 획득 가치 계산
    1-3. 최대 가치 방법 선택
2. def 유물 획득()
3. def 새로운 조각 생성()
   3-1 def 유물 획득() 후 반복
4. 5. 1 ~ 4 반복

• 1 ~ 3 단계를 반복하는 과정으로 봤다.
• 5 * 5 형태이기 때문에 9가지 중심에 대해서 3가지 회전 각도에 대해서 모두 탐색한다.
• K 도 10 이하이기 때문에 완전 탐색한다.
• 동일한 숫자 N 개 이상임을 판별하기 위해서는 DFS 를 사용하였다. 

---

📌 포인트

• 25칸 모두에 대해서 DFS 를 진행한다. 이때 이미 value 를 계산한 칸은 DFS 를 진행하면 안되기에 이중포문 밖에서의 visited 가 필요하다.
• 90도, 180도 270 도 회전은 90도를 1번, 2번, 3번 사용한 것으로 보았다.
• 회전 후 최대 가치 계산 시 Deepcopy 를 사용했기에 최대 가치의 회전을 실제 map 에 적용하는 함수가 필요했다.
• 행과 열에 대한 우선순위를 정확하게 파악하고 헷갈리지 말자.

 

---

💻  코드

# https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=1&pageSize=5

"""
1. def 탐사 진행()
    1-1. ((x, y 기준 3 * 3 회전) * 3) * 9
    1-2. def 유물 획득 가치 계산
    1-3. 최대 가치 방법 선택
2. def 유물 획득()
3. def 새로운 조각 생성()
4. def 유물 획득()
---
5. 1 ~ 4 반복
"""

import sys
from copy import deepcopy

input = sys.stdin.readline

K, M = map(int, input().split())
site = [list(map(int, input().split())) for _ in range(5)]
next_number = list(map(int, input().split()))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

new_index = 0

def calculate_value(board):
    total_remove_list = []
    value = 0
    visited2 = [[False] * 5 for i in range(5)]
    for i in range(5):
        for j in range(5):
            if visited2[i][j]:
                continue

            stack = []
            target = board[i][j]
            stack.append([i, j])
            visited = [[False] * 5 for i in range(5)]
            cnt = 0
            remove_list = []

            while stack:
                x, y = stack.pop()

                if x < 0 or x >= 5 or y < 0 or y >= 5:
                    continue

                if visited[x][y]:
                    continue

                visited[x][y] = True

                if board[x][y] == target:
                    cnt += 1
                    remove_list.append([x, y])

                    for k in range(4):
                        nx = x + dx[k]
                        ny = y + dy[k]
                        stack.append([nx, ny])

            if cnt >= 3:
                value += cnt
                total_remove_list.extend(remove_list)
                for x, y in remove_list:
                    visited2[x][y] = True

    return value, total_remove_list


def rotate_site(x, y, degree):
    copy_site = deepcopy(site)

    for _ in range(degree):
        temp = copy_site[x - 1][y]
        copy_site[x - 1][y] = copy_site[x][y - 1]
        copy_site[x][y - 1] = copy_site[x + 1][y]
        copy_site[x + 1][y] = copy_site[x][y + 1]
        copy_site[x][y + 1] = temp

        temp = copy_site[x - 1][y + 1]
        copy_site[x - 1][y + 1] = copy_site[x - 1][y - 1]
        copy_site[x - 1][y - 1] = copy_site[x + 1][y - 1]
        copy_site[x + 1][y - 1] = copy_site[x + 1][y + 1]
        copy_site[x + 1][y + 1] = temp

    return calculate_value(copy_site)


def rotate_real_site(x, y, degree):
    for _ in range(degree):
        temp = site[x - 1][y]
        site[x - 1][y] = site[x][y - 1]
        site[x][y - 1] = site[x + 1][y]
        site[x + 1][y] = site[x][y + 1]
        site[x][y + 1] = temp

        temp = site[x - 1][y + 1]
        site[x - 1][y + 1] = site[x - 1][y - 1]
        site[x - 1][y - 1] = site[x + 1][y - 1]
        site[x + 1][y - 1] = site[x + 1][y + 1]
        site[x + 1][y + 1] = temp


def exploration():
    max_value = 0
    max_index_degree = []
    remove_list = []
    for k in range(1, 4):
        for j in range(1, 4):
            for i in range(1, 4):
                v, r_l = rotate_site(i, j, k)
                if max_value < v:
                    max_value = v
                    max_index_degree = [i, j, k]
                    remove_list = r_l

    if max_value == 0:
        return max_value

    rotate_real_site(max_index_degree[0], max_index_degree[1], max_index_degree[2])

    fill_site(remove_list)

    v, rl = calculate_value(site)
    while v != 0:
        fill_site(rl)
        max_value += v
        v, rl = calculate_value(site)

    return max_value


def fill_site(rl):
    global new_index, site

    rl.sort(key=lambda x: (x[1], -x[0]))
    for x, y in rl:
        site[x][y] = next_number[new_index]
        new_index += 1


def solv():
    result = []

    for _ in range(K):
        value = exploration()
        if value == 0:
            break

        result.append(value)

    print(" ".join(map(str, result)))


solv()