[코드트리] 고대 문명 유적 탐사 (G4^ / 시뮬레이션) - Python

링크

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

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

 

 

 

 

 

문제 해석

격자 크기 5*5
유믈 조각 종류 : 7개 (1~7)

 

 

입력
첫 번째 줄 : kk mm 
  kk : 진행할 턴 횟수
  mm : 벽면 유물 조각 개수
나머지 줄 : 유물 테이블
마지막 줄 : 벽면 유물 조각 번호



출력
한 줄에 각 턴에서 획득한 유물 총합 출력
이번 턴에 획득이 불가능하면 입력 없이 그대로 종료



탐사
3*3 격자 선택
탐사는 3*3격자를 선택해서 회전 가능
시계 방향 90
시계 방향 180
시계 방향 270



한 턴에 일어나는 일
1) 탐사를 통해 회전 목표 선택
2) 유물 1차 획득
3) 연쇄 획득


- 회전 목표 선택 기준
1) 1차 유물 획득 가치 최대화
2) 회전한 각도가 가장 작은 방법
3) 열이 가장 작은 구간
4) 행이 가장 작은 구간


- 유물 1차 획득
조각이 3개 이상 연결된 경우, 조각이 유물이 되고 사라짐

조각이 사라진 위치는 새로운 조각이 생김
새로운 조각은 벽면의 숫자를 사용하며 점차 증가함

조각이 생기는 순서
1) 열 번호가 작은 순
2) 행 번호가 큰 순


- 유물 연쇄 획득
새로운 조각이 생겨난 이후 3개 이상 연결되는 케이스
조각이 모여 유물이 되고 사라짐
더이상 유물이 없어지지 않을 때까지 반복

 

 

 

 

풀이 & 코드 해석

배열 회전과 BFS가 포함된 시뮬레이션 문제입니다.

 

이외에는 문제에서 제시하는 조건에 맞춰서 코드를 작성하면 해결됩니다.

 

 

 

코드

from collections import deque


def print_arr(arrs):
    for i in range(len(arrs)):
        for j in range(len(arrs)):
            print(arrs[i][j], end=" ")
        print()


def arr_copy(arr1, arr2):
    for i in range(len(arr1)):
        for j in range(len(arr1[0])):
            arr1[i][j] = arr2[i][j]


def rotate(sx, sy, rr):
    tmp = [[0] * 3 for _ in range(3)]
    result = [[0] * 3 for _ in range(3)]

    len_tmp = 3

    for i in range(3):
        for j in range(3):
            tmp[i][j] = arr[sx + i][sy + j]

    for i in range(len_tmp):
        for j in range(len_tmp):
            if rr == 0:
                result[j][len_tmp - i - 1] = tmp[i][j] # 시계
            elif rr == 1:
                result[len_tmp - i - 1][len_tmp - j - 1] = tmp[i][j] # 시계 180
            else:
                result[len_tmp - j - 1][i] = tmp[i][j] # 시계 270

    for i in range(len_tmp):
        for j in range(len_tmp):
            arr[i + sx][j + sy] = result[i][j]


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


def bfs(x, y, c):
    global nn
    v = [[False] * nn for _ in range(nn)]
    q = deque()
    q.append([x, y, c])
    v[x][y] = True

    selected = []
    selected.append([x, y])

    while len(q) != 0:
        px, py, pc = q.popleft()

        for d in range(4):
            nx = px + dx[d]
            ny = py + dy[d]

            if nx < 0 or nx >= nn or ny < 0 or ny >= nn or v[nx][ny] == True or arr[nx][ny] != pc:
                continue

            q.append([nx, ny, pc])
            selected.append([nx, ny])
            v[nx][ny] = True

    if len(selected) >= 3:
        for ii, jj in selected:
            arr[ii][jj] = 0
        return len(selected)

    return 0


def get_value():
    global nn
    gval = 0
    for i in range(nn):
        for j in range(nn):
            if arr[i][j] != 0:
                gval += bfs(i, j, arr[i][j])

    return gval


def fill():
    global ww, nn

    for j in range(nn):
        for i in range(nn - 1, -1, -1):
            if arr[i][j] == 0:
                arr[i][j] = wall[ww]
                ww += 1


def get_real_value():
    global ans

    while True:
        now_ans = 0
        for i in range(nn):
            for j in range(nn):
                if arr[i][j] != 0:
                    now_ans += bfs(i, j, arr[i][j])
        if now_ans == 0:
            break
        else:
            # 정답 갱신
            ans += now_ans

            # 유물 채우기
            fill()


def pick():
    global nn
    pval = 0
    px = -1
    py = -1
    pr = -1
    for i in range(3):
        for j in range(3):
            for r in range(3):
                arr_copy(arr, ori_arr)

                # 이번에 찾을 위치 회전 시키기
                rotate(i, j, r)

                # 회전 시킨 유물의 1차 획득 가치 확인
                gval = get_value()

                if gval == 0:
                    continue

                if pval < gval:
                    pval = gval
                    px = i
                    py = j
                    pr = r
                elif pval == gval:
                    if pr > r:
                        px = i
                        py = j
                        pr = r
                    elif pr == r:
                        if py > j:
                            px = i
                            py = j
                            pr = r
                        elif py == j:
                            if px > i:
                                px = i
                                py = j
                                pr = r

    return px, py, pr


kk, mm = list(map(int, input().split()))

nn = 5

ori_arr = []
arr = [[0] * nn for _ in range(nn)]
v = [[False] * nn for _ in range(nn)]

for i in range(nn):
    ori_arr.append(list(map(int, input().split())))

wall = list(map(int, input().split()))
ww = 0

# 횟수만큼 반복
ss = 0
while ss < kk:
    # 회전 목표 선택
    xx, yy, rr = pick()
    
    # 회전해서 없을 수 있는 값이 없으면 끝내기
    if xx == -1:
        break

    # 회전
    arr_copy(arr, ori_arr)
    rotate(xx, yy, rr)

    # 끝까지 유물 획득
    ans = 0
    get_real_value()

    # 이번 턴에 획득한 유물이 없으면 끝내기
    if ans == 0:
        break

    # 출력
    print(ans, end=" ")

    # 원본 배열 수정
    arr_copy(ori_arr, arr)
    ss += 1

 

 

 

 

발생한 문제 & 해결 방안

이틀에 걸려서 풀었다.

 

처음에는 문제 자체를 잘못 이해해서 못 풀었고, 마지막은 중간에 예외처리를 하는 부분을 하나 빼먹어서 틀렸다.

 

처음 문제를 이해했을 때는 회전 후 합쳐지는 유물과, 이후에 연쇄되는 유물까지 더한 것이 큰 것을 선택하는 것인줄 알고 풀었다가 4번 테스트 케이스에서 틀렸다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java