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

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

Information

• 자료구조: 2차원 배열, 큐(queue)
• 알고리즘: BFS, 행렬 돌리기 테크닉, 정렬

Setup

(5, 5) 행렬을 `box`라고 이름 지었다. 전역변수로 선언함.

• (1) 탐사 진행: `(row, col)`을 기준으로 2차원 (3, 3) 배열을 90도 회전시킬 함수가 필요할 것 같다. 수험자 배려인지 행렬의 가장자리에서는 회전을 하지 않는다. 그러니가 (4번의 회전) x (9개의 회전축) = 36번 탐색하면 된다.
• (2) 유물 획득: `box[i][j]`마다 같은 숫자가 있는지 BFS로 탐색한다. 그중에서 조각이 3개 이상인 경우에만 유물을 획득한다. BFS 함수 마지막에 유물 조각의 개수도 담고 있어야 할 것 같다. 그리고 유물을 획득하고 조각이 채워지는 순서는 순서대로이므로 queue 자료구조를 이용하면 될 것 같다.
• (2.1) 유물 연쇄 획득: 새로운 유물 조각이 채워져도 3개 이상 조각이 연결되면 계속 유물을 획득한다. 반복문으로 계속 확인해주어야 할 것 같다.
• (3) 탐사 반복: $K$번의 턴에 걸쳐서 유물 탐사를 진행한다. $K$번 이전에 유물을 획득할 수 없다면(조각이 3개 이상 연결된 경우가 없는 경우) 탐사는 완전 종료된다.

탐사진행 - 행렬 회전

정사각행렬이므로 구현도 까다롭지 않다.

def rotate(x, y):
    tmp = box[x - 1][y]
    box[x - 1][y] = box[x][y - 1]
    box[x][y - 1] = box[x + 1][y]
    box[x + 1][y] = box[x][y + 1]
    box[x][y + 1] = tmp

    tmp = box[x - 1][y - 1]
    box[x - 1][y - 1] = box[x + 1][y - 1]
    box[x + 1][y - 1] = box[x + 1][y + 1]
    box[x + 1][y + 1] = box[x - 1][y + 1]
    box[x - 1][y + 1] = tmp

 

`rotate(x, y)` 함수는 `(x, y)`를 회전축으로 90도 회전하는 함수이다.

먼저 `[x][y]`의 상하좌우를 회전하는 코드를 짜고, 그다음에 `[x][y]`의 대각방향을 회전하는 코드를 작성했다.

참고로 행렬 돌리는 테크닉은 종종 나오니 익숙해지면 좋다.

 

탐사진행 - 회전목표

가능한 회전 중에서 유물가치-최소회전각도-회전 열 좌표가 작은 - 회전 행 좌표가 작은 순서대로 우선순위가 있다.

참고로 선택된 격자는 항상 회전을 진행해야하므로 회전하지 않는 경우는 생각하지 않아도 된다.

def get_max_item(box):
    candidates = []
    for i in range(1, 3 + 1):
        for j in range(1, 3 + 1):
            for r in range(1, 4 + 1):
                rotate(i, j)
                if r < 4:
                    num_items = total_items(box)
                    candidates.append((-num_items, r, j, i))
    candidates.sort()
    max_items, num_rotation, col, row = candidates[0]
    max_items *= (-1)
    return max_items, num_rotation, col, row

먼저 회전축마다 회전을 한다. 

회전이 끝나고 다시 원래 행렬로 돌아와야 하는데 구현이 귀찮으므로 4번회전한 것으로 코드 일관성을 구현했다.

그래서 `r < 4`인 경우에만 `candidates` 리스트에 저장한다.

 

유물 획득 - 1차 획득 및 조각 채우기

`[x][y]`에서부터 같은 숫자인 경우만 BFS 탐색을 하여 유물 개수(와 유물 좌표)를 저장한다.

만약 인접한 유물개수가 3개 이상인 경우 유물 획득한다. 

유물조각 번호는 항상 1 이상 7 이하의 정수이므로(입력 형식 참고) 획득하여 빈 유물 공간은 0으로 채운다.

 

인접한 유물개수가 3개 미만이라면 유물을 획득하지 않고 `box`에 아무런 변화를 주지 않는다.

def masking(visited, x, y):
    item = box[x][y]
    q = deque([(x, y)])
    visited[x][y] = True
    masked = [(x, y)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0  or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if box[nx][ny] == item and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
                masked.append((nx, ny))
    
    if len(masked) >= 3:
        for (xx, yy) in masked:
            box[xx][yy] = 0
        return len(masked)
    else:
        return 0
        
def mining(x, y):
    num_of_mining = 0
    visited = [[False for _ in range(5)] for _ in range(5)]
    for i in range(5):
        for j in range(5):
            if not visited[i][j]:
                num_of_mining += masking(visited, i, j)
    return num_of_mining

`masking()`의 return 값은 획득한 유물의 개수이다.

 

채워지는 유물조각은 queue에서 pop하여 순서대로 채운다.

이때 채워지는 순서가 행-열 순서가 아님에 유의한다.

def filling(q_num):
    for j in range(5):
        for i in range(4, -1, -1):
            if box[i][j] == 0:
                box[i][j] = q_num.popleft()

 

유물 획득 - 연쇄 획득

`while` loop를 이용하여 유물을 계속 얻을 수 있는지 확인한다.

얻을 수 있는 유물이 있다면 계속 `filling()`으로 유물을 채우고 계속 탐사-획득한다.

유물을 얻을 수 없다면 while loop을 break한다.

while True:
    num_item = mining(row, col)
    score += num_item
    if num_item > 0:
        filling(q_num)
    else:
        break

 

탐사 반복

매번 $1 \le k \le K$ 번째 탐사마다 유물을 획득한다.

$k$번째 탐사마다 얻을 수 있는 점수를 0으로 초기화한다.

 

`get_max_item(box)`를 이용하여 유물가치가 가장 큰 회전 수, 그때의 (행, 열) 좌표를 구한다.

그리고 그때의 행렬로 다시 세팅한다.

 

최적의 행렬에서 `mining()`과 `filling()`을 이용하여 유물 획득, 조각 채우기를 시뮬레이션한다.

만약 유물을 더이상 얻을 수 없다면 while loop을 break한다.

처음부터 유물을 얻을 수 없다면(`score = 0`) 탐사 전체를 종료한다. ($k \le K$이어도)

 

최종적으로 `ans` 리스트의 원소를 출력한다.

첫번째 탐사에서는 항상 유물이 발견됨을 가정해도 되므로, `ans`가 비어있는 경우는 고려하지 않아도 된다.

ans = []
for k in range(K):
    score = 0
    max_items, num_rotation, col, row = get_max_item(box)
    for _ in range(num_rotation):
        rotate(row, col)
    while True:
        num_item = mining(row, col)
        score += num_item
        if num_item > 0:
            filling(q_num)
        else:
            break

    if score == 0:
        break
    ans.append(score)

print(*ans)

 

전체 코드

from collections import deque

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

K, M = map(int, input().split())
box = []
for _ in range(5):
    box.append(list(map(int, input().split())))
numbers = list(map(int, input().split()))
q_num = deque(numbers)

def count_items(visited, x, y):
    q = deque([(x, y)])
    visited[x][y] = True
    item = box[x][y]
    item_count = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if box[nx][ny] == item and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
                item_count += 1
    if item_count >= 3:
        return item_count
    else:
        return 0

def total_items(box):
    total = 0
    visited = [[False for _ in range(5)] for _ in range(5)]
    for i in range(5):
        for j in range(5):
            if not visited[i][j]:
                total += count_items(visited, i, j)
    return total

def rotate(x, y):
    tmp = box[x - 1][y]
    box[x - 1][y] = box[x][y - 1]
    box[x][y - 1] = box[x + 1][y]
    box[x + 1][y] = box[x][y + 1]
    box[x][y + 1] = tmp

    tmp = box[x - 1][y - 1]
    box[x - 1][y - 1] = box[x + 1][y - 1]
    box[x + 1][y - 1] = box[x + 1][y + 1]
    box[x + 1][y + 1] = box[x - 1][y + 1]
    box[x - 1][y + 1] = tmp

def get_max_item(box):
    candidates = []
    for i in range(1, 3 + 1):
        for j in range(1, 3 + 1):
            for r in range(1, 4 + 1):
                rotate(i, j)
                if r < 4:
                    num_items = total_items(box)
                    candidates.append((-num_items, r, j, i))
    candidates.sort()
    max_items, num_rotation, col, row = candidates[0]
    max_items *= (-1)
    return max_items, num_rotation, col, row

def masking(visited, x, y):
    item = box[x][y]
    q = deque([(x, y)])
    visited[x][y] = True
    masked = [(x, y)]
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0  or nx >= 5 or ny < 0 or ny >= 5:
                continue
            if box[nx][ny] == item and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny))
                masked.append((nx, ny))
    
    if len(masked) >= 3:
        for (xx, yy) in masked:
            box[xx][yy] = 0
        return len(masked)
    else:
        return 0

def mining(x, y):
    num_of_mining = 0
    visited = [[False for _ in range(5)] for _ in range(5)]
    for i in range(5):
        for j in range(5):
            if not visited[i][j]:
                num_of_mining += masking(visited, i, j)
    return num_of_mining

def filling(q_num):
    for j in range(5):
        for i in range(4, -1, -1):
            if box[i][j] == 0:
                box[i][j] = q_num.popleft()

ans = []
for k in range(K):
    score = 0
    max_items, num_rotation, col, row = get_max_item(box)
    for _ in range(num_rotation):
        rotate(row, col)
    while True:
        num_item = mining(row, col)
        score += num_item
        if num_item > 0:
            filling(q_num)
        else:
            break

    if score == 0:
        break
    ans.append(score)

print(*ans)