[코드트리/python] 고대 문명 유적 탐사(2024년 상반기 삼성기출)

https://www.codetree.ai/ko/frequent-problems/problems/ancient-ruin-exploration/description?introductionSetId=&bookmarkId=

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

문제

수천 년 동안 잊혀진 고대 문명의 유적을 발견하게 되었습니다. 이 유적지는 5×5 격자 형태로 되어 있으며, 각 칸에는 다양한 유물의 조각이 배치되어 있습니다. 유물 조각은 총 7가지 종류로, 각각 숫자 1부터 7로 표현됩니다.

[1] 탐사 진행

3×3 격자 선택

당신은 고고학자로서 5×5 격자 내에서 3×3 격자를 선택하여 격자를 회전시킬 수 있습니다. 선택된 격자는 시계 방향으로 90도, 180도, 270도 중 하나의 각도만큼 회전시킬 수 있습니다. 단, 선택된 격자는 항상 회전을 진행해야만 합니다.

예를 들어, 다음과 같이 유적지가 존재한다고 가정해보겠습니다.

만약 회전 중심 좌표를 (3,3)으로 설정하고, 90도 회전하면 유적지는 다음과 같이 바뀌게 됩니다.

회전 목표

가능한 회전의 방법 중 (1) 유물 1차 획득 가치를 최대화하고, 그러한 방법이 여러가지인 경우 (2) 회전한 각도가 가장 작은 방법을 선택합니다. 그러한 경우도 여러가지인 경우 (3) 회전 중심 좌표의 열이 가장 작은 구간을, 그리고 열이 같다면 행이 가장 작은 구간을 선택합니다.

[2] 유물 획득

유물 1차 획득

상하좌우로 인접한 같은 종류의 유물 조각은 서로 연결되어 있습니다. 이 조각들이 3개 이상 연결된 경우, 조각이 모여 유물이 되고 사라집니다. 유물의 가치는 모인 조각의 개수와 같습니다.

예를 들어, 아래와 같이 유적지가 존재한다면 유물은 총 7개의 조각으로 이루어지게 됩니다.

각각 3개, 4개의 조각이 모이므로 얻게 되는 유물의 가치는 총 7이 됩니다.

이 유적지에서 유물이 사라지고 난 이후의 모습은 다음과 같습니다.

유적의 벽면에는 1부터 7 사이의 숫자가 M개 적혀 있습니다. 이들은 유적에서 조각이 사라졌을 때 새로 생겨나는 조각에 대한 정보를 담고 있습니다.

예를 들어, 유적의 벽면에 아래와 같이 새로 생겨나는 조각에 대한 정보는 아래와 같습니다.

조각이 사라진 위치에는 유적의 벽면에 적혀있는 순서대로 새로운 조각이 생겨납니다. 새로운 조각은 (1) 열 번호가 작은 순으로 조각이 생겨납니다. 만약 열 번호가 같다면 (2) 행 번호가 큰 순으로 조각이 생겨납니다. 단, 벽면의 숫자는 충분히 많이 적혀 있어 생겨날 조각의 수가 부족한 경우는 없다고 가정해도 좋습니다.

위의 예시에서 새로운 조각들이 채워지는 방법에 따른 순서를 나타내면 다음과 같습니다.

따라서 조각은 아래와 같이 채워집니다.

단, 유적의 벽면에 써 있는 숫자를 사용한 이후에는 다시 사용할 수 없으므로 이후 부터는 남은 숫자부터 순서대로 사용합니다. 즉, 이후에는 아래 그림에서 8번째로 적혀있는 수인 1부터 다시 사용이 가능합니다.

유물 연쇄 획득

새로운 유물 조각이 생겨난 이후에도 조각들이 3개 이상 연결될 수 있습니다. 이 경우 앞과 같은 방식으로 조각이 모여 유물이 되고 사라집니다. 사라진 위치에는 또다시 새로운 조각이 생겨나며 이는 더 이상 조각이 3개 이상 연결되지 않아 유물이 될 수 없을 때까지 반복됩니다.

위의 예시에서는 새로운 유물 조각이 생겨난 이후에도 다음과 같이 유물이 만들어집니다. 따라서 연쇄적으로 유물을 획득하는 과정을 반복해야 합니다.

[3] 탐사 반복

이 문제에서는 탐사 진행 ~ 유물 연쇄 획득의 과정까지를 1턴으로 생각하며, 총 K 번의 턴에 걸쳐 진행됩니다.

각 턴마다 획득한 유물의 가치의 총합을 출력하는 프로그램을 작성해야 합니다. 단, 아직 K번의 턴을 진행하지 못했지만, 탐사 진행 과정에서 어떠한 방법을 사용하더라도 유물을 획득할 수 없었다면 모든 탐사는 그 즉시 종료됩니다. 이 경우 얻을 수 있는 유물이 존재하지 않음으로, 종료되는 턴에 아무 값도 출력하지 않음에 유의합니다.

입력

첫 번째 줄에 탐사의 반복 횟수 K와 벽면에 적힌 유물 조각의 개수 M이 공백을 사이에 두고 주어집니다.

그 다음 5개의 줄에 걸쳐 유물의 각 행에 있는 유물 조각에 적혀 있는 숫자들이 공백을 사이에 두고 순서대로 주어집니다.

그 다음 줄에는 벽면에 적힌 M개의 유물 조각 번호가 공백을 사이에 두고 순서대로 주어집니다.

단, 초기에 주어지는 유적지에서는 탐사 진행 이전에 유물이 발견되지 않으며, 첫 번째 턴에서 탐사를 진행한 이후에는 항상 유물이 발견됨을 가정해도 좋습니다.

출력

첫 번째 줄에 각 턴 마다 획득한 유물의 가치의 총합을 공백을 사이에 두고 출력합니다.

---

예제

2 20
7 6 7 6 7
6 7 6 7 6
6 7 1 5 4
7 6 3 2 1
5 4 3 2 7
3 2 3 5 2 4 6 1 3 2 5 6 2 1 5 6 7 1 2 3

17

---

해설

소요시간: 3시간

주요 포인트

- 2차원 회전(90, 180, 270)

- "1차 획득 가치" 우선순위에 따른 저장 방식

- 재사용 가능 단위로 함수 쪼개기(각도 돌리기, 유물 찾기, 유물 제거, 벽면 채우기) 5단계로 분할

---

1) 최대 유물 1차 획득

- (3x3) 맵으로 5x5맵을 다 돌려면 9번

- 각도 3번

9*3 = 27 맵으로 완전탐색 계획 수립

완전탐색 이유: 시간복잡도 너무 충분

 

유물 기록을 돌리되, 이때 sort() 조건을 우선순위로 처리

 

1) 유물 1차 획득 가치 최대화

2) 각도 작은 순

3) 열이 작은 순

4) 행이 작은 순

max_ancients = [] # 최대 고대 유물 기록지
    for i in range(3):
        for j in range(3):
            # 1) 90도 1차 획득 
            c_mat = rotate_90(i, j)
            max_ancients.append((bfs_first_gain(c_mat, 90, i+1, j+1))) # 회전각, 중심x, 중심y
            
            # 2) 180도 1차 획득 
            c_mat = rotate_180(i, j)
            max_ancients.append((bfs_first_gain(c_mat, 180, i+1, j+1))) # 회전각, 중심x, 중심y

            # 3) 270도 1차 획득 
            c_mat = rotate_270(i, j)
            max_ancients.append((bfs_first_gain(c_mat, 270, i+1, j+1))) # 회전각, 중심x, 중심y
    max_ancients.sort(key = lambda x:(-x[0], x[1], x[3], x[2])) # # 유물 총 가치, 각도, 중심y, 중심x

 

1차 획득 가능 유물 없으면 K번 도는 중에 탈출

 

유물 획득한다면  

1) 1차 획득 가치 최대에 맞게 각도 다시 돌리기

2) 유물 다시 찾기

3) 유물 제거

4) 점수 update

5) 벽면으로 값 채워주기

# 1) 획득가능한 유물이 없다면
    if max_ancients[0][0] == 0: 
        break 
    else:
        # 1) 다시 각도 돌리기 
        angle = max_ancients[0][1]
        x, y = max_ancients[0][2]-1, max_ancients[0][3]-1
        if angle == 90:
            c_mat = rotate_90(x, y)
        elif angle == 180:
            c_mat = rotate_180(x, y)
        else: 
            c_mat = rotate_270(x, y)
        mat = [arr[:] for arr in c_mat] # deep copy

        temp_result = 0
        while True:
            # 2) 유물 여러개 찾기
            record = bfs_resarch(x, y) 
            if record == []: # 더 이상 유물없으면
                break 

            # 3) 해당 유물 제거 
            cnt, delete_ancients = bfs_delete(record) 
            delete_ancients.sort(key = lambda x : (x[1], -x[0])) # 열 번호가 작은 순, 행 번호가 큰 순
            
            # 4) 점수 update
            temp_result += cnt

            # 5) 벽면으로 채우기 
            wall_charge(delete_ancients)

        result.append(temp_result)

---

전체코드

from collections import deque 
K, M = map(int, input().split()) # 탐사횟수, 유물 조각의 개수 

mat = [0]*5
move = [(0,-1),(0,1),(-1,0),(1,0)]
for i in range(5):
    mat[i] = list(map(int, input().split()))
wall_ancients = deque(list(map(int, input().split())))

def rotate_90(x, y):
    c_mat = [arr[:] for arr in mat] 
    cc_mat = [[0]*3 for _ in range(3)]
    
    # 1) 90도 회전 
    for i in range(3):
        for j in range(3):
            cc_mat[j][2-i] = mat[x+i][y+j]

    # 2) 각도 적용시키기 
    for i in range(3):
        for j in range(3):
            c_mat[x+i][y+j] = cc_mat[i][j]

    return c_mat

def rotate_180(x, y):
    c_mat = [arr[:] for arr in mat] 
    cc_mat = [[0]*3 for _ in range(3)]

    # 1) 180도 회전 
    for i in range(3):
        for j in range(3):
            cc_mat[2-i][2-j] = mat[x+i][y+j]

    # 2) 각도 적용시키기 
    for i in range(3):
        for j in range(3):
            c_mat[x+i][y+j] = cc_mat[i][j]

    return c_mat

def rotate_270(x, y):
    c_mat = [arr[:] for arr in mat] 
    cc_mat = [[0]*3 for _ in range(3)]

    # 1) 270도 회전 
    for i in range(3):
        for j in range(3):
            cc_mat[2-j][i] = mat[x+i][y+j]

    # 2) 각도 적용시키기 
    for i in range(3):
        for j in range(3):
            c_mat[x+i][y+j] = cc_mat[i][j]

    return c_mat

def bfs_first_gain(c_mat, angle, m_x, m_y): # 유물 1차 획득 

    visited = [[False]*5 for _ in range(5)]
    cnt = 1
    result = 0

    for i in range(5):
        for j in range(5):
            if not visited[i][j]:
                cnt = 1
                que = deque()
                que.append((i,j))
                visited[i][j] = True

                while que:
                    x, y = que.popleft()
                    for dx, dy in move:
                        px, py = x+dx, y+dy
                        if 0<=px<5 and 0<=py<5 and not visited[px][py] and c_mat[px][py] == c_mat[i][j]:
                            que.append((px, py))
                            cnt += 1
                            visited[px][py] = True 

                # 유물이 3개 이상이라면
                if cnt >= 3: 
                    result += cnt # 유물가치
    
    return [result, angle, m_x, m_y] # 유물 총 가치, 각도, 중심x, 중심y 

def bfs_resarch(x, y):
    record = [] # 3개 이상의 유물 기록

    visited = [[False]*5 for _ in range(5)]
    cnt = 1
    for i in range(5):
        for j in range(5):
            cnt = 1
            que = deque()
            que.append((i,j))
            visited[i][j] = True

            while que:
                x, y = que.popleft()
                for dx, dy in move:
                    px, py = x+dx, y+dy
                    if 0<=px<5 and 0<=py<5 and not visited[px][py] and mat[px][py] == mat[i][j]:
                        que.append((px, py))
                        cnt += 1
                        visited[px][py] = True  

            # 유물이 3개 이상이라면
            if cnt >= 3: 
                record.append((i,j))
    return record

def bfs_delete(record):
    delete_ancients = []
    cnt = len(record)

    for r in record:
        que = deque()
        que.append((r[0], r[1]))
        visited = [[False]*5 for _ in range(5)]
        visited[r[0]][r[1]] = True
        target = mat[r[0]][r[1]]
        mat[r[0]][r[1]] = 0
        delete_ancients.append((r[0], r[1]))

        while que:
            x, y = que.popleft()
            for dx, dy in move:
                px, py = x+dx, y+dy
                if 0<=px<5 and 0<=py<5 and not visited[px][py] and mat[px][py] == target:
                    que.append((px, py))
                    visited[px][py] = True 
                    mat[px][py] = 0 # 지우기
                    delete_ancients.append((px, py)) # 다시 유물로 채우기 위한 자리 기억
                    cnt += 1

    return cnt, delete_ancients 

def wall_charge(d_a):
    for i in range(len(d_a)):
        value = wall_ancients.popleft()
        mat[d_a[i][0]][d_a[i][1]] = value 

result = []
for q in range(K):

    max_ancients = [] # 최대 고대 유물 기록지
    for i in range(3):
        for j in range(3):
            # 1) 90도 1차 획득 
            c_mat = rotate_90(i, j)
            max_ancients.append((bfs_first_gain(c_mat, 90, i+1, j+1))) # 회전각, 중심x, 중심y
            
            # 2) 180도 1차 획득 
            c_mat = rotate_180(i, j)
            max_ancients.append((bfs_first_gain(c_mat, 180, i+1, j+1))) # 회전각, 중심x, 중심y

            # 3) 270도 1차 획득 
            c_mat = rotate_270(i, j)
            max_ancients.append((bfs_first_gain(c_mat, 270, i+1, j+1))) # 회전각, 중심x, 중심y
    max_ancients.sort(key = lambda x:(-x[0], x[1], x[3], x[2])) # # 유물 총 가치, 각도, 중심y, 중심x 

    # 1) 획득가능한 유물이 없다면
    if max_ancients[0][0] == 0: 
        break 
    else:
        # 1) 다시 각도 돌리기 
        angle = max_ancients[0][1]
        x, y = max_ancients[0][2]-1, max_ancients[0][3]-1
        if angle == 90:
            c_mat = rotate_90(x, y)
        elif angle == 180:
            c_mat = rotate_180(x, y)
        else: 
            c_mat = rotate_270(x, y)
        mat = [arr[:] for arr in c_mat] # deep copy

        temp_result = 0
        while True:
            # 2) 유물 여러개 찾기
            record = bfs_resarch(x, y) 
            if record == []: # 더 이상 유물없으면
                break 

            # 3) 해당 유물 제거 
            cnt, delete_ancients = bfs_delete(record) 
            delete_ancients.sort(key = lambda x : (x[1], -x[0])) # 열 번호가 작은 순, 행 번호가 큰 순
            
            # 4) 점수 update
            temp_result += cnt

            # 5) 벽면으로 채우기 
            wall_charge(delete_ancients)

        result.append(temp_result)

print(*result)

 

---

실수 내용 + 자가 피드백

- 함수화 해서 디버깅하니까 보기 너무 편했음👍

- (행, 열) 우선순위를 자꾸 섞어주니까 헷갈려서 행열을 바꿔버림, 이제부터는 주관대로(x, y) 순으로 항상 변수 가져갈 것

- 여러 개의 bfs를 돌리다 보니, 복붙을 하는데 (i, j)를 쓰지도 않는데 복붙 해서 디버깅 지역 찾기 어려웠음

- 복붙 할 때, 항상 의심할 것 => 해당 bfs()로 이미지 전환 빠르게 진행할 것

- 함수에서 리스트 반환할 때, Call by assignment이다. 따라서 값이 바뀌면 객체가 같이 바뀌는데 현재는 재사용 로직에서 이를 바꿔도 문제가 없는데 다른 문제에서 주의할 것 

 

---

참고

https://codewizard.tistory.com/56

[Python] 파이썬의 함수 인자 전달 방식(Call by Assignment)