[코드트리][기출문제] 고대 문명 유적 탐사

자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)

문제

코드트리 고대 문명 유적 탐사

문제 풀이 및 회고

추가적인 연산을 하지 않고 필요한 모듈만 코딩을 해서 코드를 짜보았다.

코드(python)

from collections import deque

def find_remove(board: list) -> list:
    """
    loc에서 시작해서 3개이상 붙어있는 모든 애들 찾기
    """
    remove_things = []
    visited = [[0]*5 for _ in range(5)] # 방문여부 확인하기 위해
    
    dy, dx = [1,-1,0,0], [0,0,1,-1]
    def bfs(loc: list):
        """
        loc에 있는 값과 동일한 곳들이 3개 이상 붙어있으면 결과값에 추가하기
        """
        nonlocal board, dy, dx, visited
        q = deque()
        q.append(loc)
        value = board[loc[0]][loc[1]] # loc 값
        visited[loc[0]][loc[1]] = 1 # 방문처리
        locations = [] # 제거할 곳
        locations.append(loc)
        while q:
            y, x = q.popleft()
            for i in range(4):
                ny, nx = y+dy[i], x+dx[i]
                if ny < 0 or nx < 0 or ny >= 5 or nx >= 5: # 격자 밖이라 고려 X
                    continue
                if visited[ny][nx] == 0 and board[ny][nx] == value: # board에 loc값과 동일하면서 아직 방문 안해봄
                    visited[ny][nx] = 1 # 방문처리
                    q.append([ny, nx]) # 다음 고려할 곳
                    locations.append([ny, nx]) # 지워야할 곳인지 확인하기 위해서 
        
        return locations if len(locations) >= 3 else None # 연결된 곳이 3개 이상이면 지울거임
    
    for i in range(5):
        for j in range(5):
            if visited[i][j] == 0:
                locations = bfs([i,j])
                if locations:
                    remove_things += locations

    return remove_things

def rotate_board(board: list, loc: list, rot: int) -> list:
    """
    5*5 행렬에서 loc 기준으로(loc가 중심점임) 3*3 행렬을 부분적으로 돌리기
    """
    y, x = loc
    result = [board[i][:] for i in range(5)]
    if rot == 90: # 90도 회전
        for i in range(3):
            for j in range(3):
                result[y-1+i][x-1+j] = board[y-1+2-j][x-1+i]
    elif rot == 180: # 180도 회전
        for i in range(3):
            for j in range(3):
                result[y-1+i][x-1+j] = board[y-1+2-i][x-1+2-j]
    elif rot == 270: # 270도 회전
        for i in range(3):
            for j in range(3):
                result[y-1+i][x-1+j] = board[y-1+j][x-1+2-i]
    return result

def show_board(board: list):
    """
    디버깅을 위해 board 보여주는 함수
    """
    for i in range(5):
        print(board[i])
    print("========================================================")
    return None

def find_max(board: list):
    """
    # 유물 갯수 / 회전각도 작은거 / 중심좌표 열(x) 작은거 / 행(y)이 작은거 기준으로 가장 점수가 높은 곳 찾기
    """
    results = [360, 4, 4]
    remove_locations = []
    for i in range(3):
        for j in range(3):
            loc = [i+1, j+1]

            for r in range(3):
                rot_board = rotate_board(board, loc, 90*(r+1))
                rot_locations = find_remove(rot_board)
                if rot_locations:
                    if len(rot_locations) > len(remove_locations): # 유물 갯수 많은거
                        remove_locations = rot_locations
                        results = [90*(r+1), j+1, i+1]
                    # 회전각도 작은거 / 중심좌표 열(x) 작은거 / 행(y)이 작은거
                    elif len(rot_locations) == len(remove_locations) and min(results, [90*(r+1), j+1, i+1]) != results: 
                        remove_locations = rot_locations
                        results = [90*(r+1), j+1, i+1]
    return remove_locations, results


def solution(board: list, k: int, items: list):
    """
    k 회 turn 내에 점수 나는지 확인
    """
    items_idx = 0

    def refill_item(locations:list):
        nonlocal items_idx, items, board
        for loc in locations:
            board[loc[0]][loc[1]] = items[items_idx]
            items_idx += 1
        return None

    #show_board(board)

    cnt = 0
    while cnt != k: # k회 실행
        cnt += 1
        # 탐사 진행.
        remove_locations, info = find_max(board) #회전해서 가장 우선순위 높은 친구 고르기
        if remove_locations == []: # 더 점수를 얻을 유물이 없음
            break
        remove_locations.sort(key=lambda x:(x[1], -x[0]))
        now_score = 0
        board = rotate_board(board, [info[2], info[1]], info[0]) # 유물 얻은 board로 변경
        now_score += len(remove_locations)
        refill_item(remove_locations)
        #show_board(board)

        while True: # 유물 연쇄 획득 과정
            remove_locations = find_remove(board)
            if remove_locations == []: # 더 점수를 얻을 유물이 없음
                break
            remove_locations.sort(key=lambda x:(x[1], -x[0]))
            now_score += len(remove_locations)
            refill_item(remove_locations)
            #show_board(board)
        
        print(now_score, end=" ") #  번째 줄에 각 턴 마다 획득한 유물의 가치의 총합을 공백을 사이에 두고 출력
        #show_board(board)
        

if __name__ == "__main__":
    K, M = map(int, input().split()) # 탐사 반복횟수 K, 벽면에 적힌 유물 조각의 개수 M
    board = [list(map(int, input().split())) for _ in range(5)] # 5개 줄 유물 정보
    items = list(map(int, input().split()))
    solution(board, K, items)