[코드트리] 고대 문명 유적 탐사 - 파이썬

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/ancient-ruin-exploration/description

코딩테스트 기출 문제 설명: 고대 문명 유적 탐사 | 코드트리

---

from collections import deque

def is_range(r,c):
    return 0<=r<5 and 0<=c<5
dx = [1,-1,0,0]
dy = [0,0,1,-1]
angle_list = [90, 180, 270]

def rotate_90(arr, x, y):
    new_arr = [row[:] for row in arr]  # 깊은 복사
    
    # (x, y) 중심의 3x3 영역 추출
    sub = [[arr[i][j] for j in range(y-1, y+2)] for i in range(x-1, x+2)]
    
    # 3x3 회전
    rotated = [[0]*3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            rotated[j][3-i-1] = sub[i][j]
    
    # 회전된 3x3 영역을 다시 new_board에 반영
    for i in range(3):
        for j in range(3):
            new_arr[x-1+i][y-1+j] = rotated[i][j]
    
    return new_arr
   
def rotate(ang, arr, x, y):
    new_arr = [row[:] for row in arr]
    num = angle_list.index(ang)+1
    for _ in range(num):
        new_arr = rotate_90(new_arr, x, y)
    return new_arr

def bfs(x,y,visited, arr):
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    piece_coord = [[x,y]] # 원래 배열에서 유적조각 비워야해서
    value = arr[x][y]
    while q:
        cx, cy= q.popleft()
        for d in range(4):
            nx, ny = cx+dx[d], cy+dy[d]
            if is_range(nx, ny) and not visited[nx][ny] and arr[nx][ny] == value:
                visited[nx][ny] = True
                q.append((nx, ny))
                piece_coord.append((nx, ny))
    return piece_coord if len(piece_coord) >= 3 else []

# 유물조각의 좌표를 찾기
def search_relic(arr):
    visited = [[False]*5 for _ in range(5)]
    all_piece = [] # 유물조각이 존재하는 좌표, 빈칸을 채울때 사용
    for i in range(5):
        for j in range(5):
            if not visited[i][j]:
                res = bfs(i,j,visited, arr)
                if res:
                    all_piece.extend(res)
    return all_piece


def get_relic(arr):
    # 서로 연결된 유물 조각 찾기 -> 유물 가치 더함 -> 유물 조각 없앰 -> 빈 상태로 리턴
    relics = search_relic(arr)
    return len(relics), sorted(relics, key=lambda x: (x[1], -x[0])) # 유물좌표의 총 개수, 조건에 맞춘 유물좌표 리스트 

# 유물 삭제 및 채움
def process_relics(relics, arr):
    for i, j in relics:
        arr[i][j] = piece.pop(0)
    return arr

def get_sequence_relic(relics, arr):
    arr = process_relics(relics, arr)
    total = 0
    while True:
        rel_value, relics = get_relic(arr)
        if rel_value == 0:
            break
        total += rel_value
        arr = process_relics(relics, arr)
    return arr, total

def exploration():
    # 회전할 중심좌표 선택 -> 회전 -> 유물획득 -> 각도 최소, 열 작게, 행 작게 
    candidate = []
    for i in range(1,4):
        for j in range(1,4):
            for ang in angle_list:
                new_arr = rotate(ang, arr, i, j)
                rel_value, relics = get_relic(new_arr)
                if rel_value > 0:
                    candidate.append([rel_value, ang, j, i, new_arr, relics])
    
    if not candidate:
        return 0,0,0,0,0,0
    candidate.sort(key=lambda x: (x[0], -x[1], -x[2], -x[3]), reverse=True)

    return candidate[0] # 회전 중심이 되는 


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

# 메인 루프
result = []
for _ in range(K):
    value, angle, x, y, arr, relics = exploration()
    if arr == 0:
        break
    arr, seq_value = get_sequence_relic(relics, arr)
    result.append(str(value+seq_value))

print(" ".join(result))