[Python] 코드트리 - 고대 문명 유적 탐사

 

 

https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration?&utm_source=clipboard&utm_medium=text

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

 

 

문제 3줄 요약

1. 유적지에서 탐사를 통해 유물 조각을 연결하고 발굴하고자 한다.

2. 탐사 진행, 유물 획득을 반복 과정을 거친다.

3. 턴마다 획득한 유물 가치의 총합을 출력하라.

 

---

 

삼성 예전 기출문제부터 풀고 있는데,

최근 기출 문제가 더욱 어려운 느낌이 듭니다.. ㅠ

 

탐사 진행 기능부터

천천히 살펴봅시다.

 

 

유적지는 5X5 격자로 고정되어 있으며,

탐색 과정에서는 3X3 격자를 회전시켜 유물 1차 획득 가치를 최대화 하려고합니다.

 

회전 목표를 살펴봅시다.

 

[1]

만약 유물 1차 획득 가치의 최댓값이 동일하다면,

회전한 각도가 가장 작은 방법을..!

 

[2]

그 마저도 여러가지 경우라면,

회전 중심의 열, 행 좌표가 가장 작은 구간을 선택해야합니다.

 

이 회전 목표가 충족이 안됐을 경우에

테스트 케이스 6번과 10번이 통과가 되지 않았던 것 같네요!

 

회전은 3X3으로

모양이 고정되어있어서 90, 180, 270 도에서의 좌표 이동을

하드 코딩해서 넣어줬습니다.

 

---

 

 

두 번째 유물 획득입니다.

 

탐사 과정에서 유물 1차 획득도 해당되는데요.

상하좌우로 인접한 같은 종류의 유물 조각이 3개 이상 연결된 경우,

유물을 발굴하고 가치를 조각 갯수만큼 증가시킵니다.

 

 

발굴하고 비어있는 칸은

유적의 벽면에 적혀있는 순서대로 조각을 추가합니다.

 

유적지에 추가하는 순서는

1. 열 번호가 작은 순

2. 행 번호가 큰 순

입니다.

 

벽면의 숫자는 부족한 경우가 없다는 점!

 

여기까지 진행했다면,

유물 1차 획득은 완료됐습니다.

 

다음은 유물을 채우고 난 후 유물 연쇄 획득인데요.

 

다시 유적지에 연결된 유물 조각이 3개 이상인 경우 발굴해줍니다.

연결된 유물이 없을 때 가지 반복해주면

끝.

 

---

 

 

이제 위 과정을 K번 반복해주면 되겠습니다.

다만 탐사 진행 과정에서 유물을 획득할 수 없다면,

그 즉시 종료해야하며 종료한 턴에는 아무 값도 출력하지 않아야합니다.

 

위 내용을 코드로 정리해보겠습니다.

 

from collections import deque

## [1] 탐사 진행 - 회전
## 90, 180, 270도 회전
def turn(relics, tx, ty, pos):
    turn_relics = [r.copy() for r in relics]
    rotate = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,0], [0,1], [1,-1], [1,0], [1,1]]
    
    for idx, p in enumerate(pos):
        x, y = rotate[idx][0]+tx, rotate[idx][1]+ty
        dx, dy = rotate[p-1][0]+tx, rotate[p-1][1]+ty
        turn_relics[x][y] = relics[dx][dy]

    return turn_relics

## [1] 탐사 진행
## 정해진 위치의 중심 좌표들을 기준으로 3X3 회전
def turn_relic(relics, position):
    turn_point = [[x,y] for x in range(1,4) for y in range(1,4)]
    max_cnt, degree, x, y = 0, 3, 0, 0

    for tx, ty in turn_point:
        for deg in range(len(position)):
            turn_relics = turn(relics, tx, ty, position[deg]) ## 3X3 회전
            cnt, _ = get_relic(turn_relics) ## 1차 유물 획득

            ## 회전 목표 ##
            if max_cnt < cnt:
                max_cnt = cnt
                degree = deg
                x, y = tx, ty

            elif max_cnt == cnt:
                max_cnt = cnt
                if degree == deg:
                    if y == ty:
                        if x > tx: x, y = tx, ty  
                    if y > ty: x, y = tx, ty

                if degree > deg:
                    degree = deg
                    x, y = tx, ty

    return degree, x, y

## [2] 유물 획득 - 벽면 숫자 채우기
## deque 구조 - popleft() 로 선입선출
def fill_relic(relics, piece_num, mining_root):
    for r in mining_root:
        relics[r[0]][r[1]] = piece_num.popleft()
    return


## [2] 유물 획득
## BFS를 활용한 3개 이상 연결된 유물 조각 탐색
def get_relic(relics):
    cnt, total_root, visited = 0, [], [[0]*5 for _ in range(5)]
    d = [[0,1], [1,0], [0,-1], [-1,0]]

    for x in range(5):
        for y in range(5):
            if visited[x][y]: continue

            relic, deq, r_cnt, root = relics[x][y], deque([[x,y]]), 1, [[x,y]]
            visited[x][y] = r_cnt

            while deq:
                i, j = deq.popleft()

                for dx, dy in d:
                    nx, ny = i+dx, j+dy
                    if 0<=nx<5 and 0<=ny<5 and relics[nx][ny]==relic and not visited[nx][ny]:
                        r_cnt += 1
                        deq.append([nx, ny])
                        visited[nx][ny] = r_cnt
                        root.append([nx, ny])

            if r_cnt >= 3:
                total_root += root
                cnt += r_cnt

    return cnt, sorted(total_root, key=lambda x:(x[1], -x[0]))

"""
초기 값
K : 탐사의 반복 횟수, M : 벽면에 적힌 유물 조각의 개수
relics : 유적지의 적혀있는 유물 조각 숫자 리스트
piece_num : 벽면에 적힌 M개의 유물 조각 번호
"""
K, M = map(int, input().split())
relics = [list(map(int, input().split())) for _ in range(5)]
piece_num = deque(map(int, input().split()))

"""
3X3 격자 회전 좌표
position : 90, 180, 270도 회전 시 기존 좌표의 이동 하드 코딩
"""
position = [[7,4,1,8,5,2,9,6,3], [9,8,7,6,5,4,3,2,1], [3,6,9,2,5,8,1,4,7]]

"""
[K번 탐사]

1. 탐사 진행 (격자 회전 및 1차 유물 획득 비교)
    1-1. 기존 유물 조각 리스트 회전

2. 유물 획득
    2-1. 벽면에 적힌 번호 채우기
    2-2. 유물이 없는 경우 종료

3. 탐사 반복

4. 출력
"""
for _ in range(K):
    answer = 0

    deg, x, y = turn_relic(relics, position)
    relics = turn(relics, x, y, position[deg])
    cnt, mining_root = get_relic(relics)
    fill_relic(relics, piece_num, mining_root)
    answer += cnt

    if not cnt: break

    while cnt>0:
        cnt, mining_root = get_relic(relics)
        fill_relic(relics, piece_num, mining_root)
        answer += cnt

    if answer: print(answer, end=' ')

 

상세한 조건들이 만족이 되지 않으면,

테스트케이스가 통과되지 않았던 것 같습니다!!

 

조건을 차근차근 하나씩 구현해나가고

BFS를 활용해 풀 수 있는 문제였습니다.

 

물론...

매우 헷갈리고 어려웠네요 ㅠㅠ

 

연습하다면 늘 것이라 믿고..

오늘은

 

끝.