[코드트리] 고대 문명 유적 탐사 - Python(파이썬)

문제

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

풀이

아이디어

나에게 삼십분만 더 있었더라면 풀 수 있었다고 너무너무 아쉬워했던 문제.

그동안 취직도 하고 많은 일을 하느라 어디서 잘 못 풀었는지는 기억이 안난다.

그냥 새로 본다고 생각하고 문제를 풀었다.

삼성문제는 갈 수록 어려워 지긴 하지만, 1번 문제는 유형이 비슷하게 느껴지기 때문에 연습만 많이 하면 풀이 시간을 좀 더 줄일 수 있을 것 같다.

✔️ 할일

• 탐사 진행
• 회전
• 유물조각 획득
• 연쇄작용

탐사진행

1. 회전할 중심 좌표를 선택
2. 회전
3. 유물 획득
4. 유물 획득 가치, 회전각도, 중심좌표( 열, 행), board 순으로 정렬 후, max를 반환

할 일은 4가지로 나눴지만, 크게 보면 [탐사진행 → 유물 연쇄 획득]으로 나눌 수 있다.

탐사 진행하면서 해야할 일도 4가지나 되니까 각각 함수를 잘 짜서 디버깅이 쉽도록 하는 것이 필요하다.

1. 회전 중심 좌표 선택

3x3 격자를 중심좌표 기준으로 회전해야 하기때문에 가장 마지막 행과 열은 제외시켜야 한다

→ for문을 돌 범위를 (1, 4)로 조정한다

모든 중심 좌표에서 90, 180, 270도를 회전해 보고, 유물 가치를 가장 최대화 할 수 있는 각을 선택해야한다. 회전 함수는 90도를 도는 함수를 만들어서 재사용 하는 방법을 이용한다.

2. 회전

그동안 연습할 때, 회전을 항상 가장 위, 가장 왼쪽 열을 기준으로 반복문을 돌았다.

이 지점을 생각을 안해서 간단한 함수를 꽤 오래 생각했다.

중심 좌표를 기준으로 회전을 하도록 만들었기 때문에, 일반화하는 것이 힘들었다.

결국 수학적 공식 까지 가져와서 회전..

# x, y 기준 3x3 격자를 90도 회전하는 함수
def rotate_90(board, x, y):
    new_board = [[0] * 5 for _ in range(5)]

    for i in range(5):
        for j in range(5):
            # new_board[x + i]
            if i <= x + 1 and i >= x - 1 and j <= y + 1 and j >= y - 1:

                new_x = x + (j-y)
                new_y = y-(i-x)
                new_board[new_x][new_y] = board[i][j]
            else:
                new_board[i][j] = board[i][j]
    return new_board

다 풀고 확인해보니 중심 좌표 말고, 가장 위, 가장 왼쪽 열을 시작으로 하면 쉽게 풀 수 있었다.

# 가장 왼쪽, 가장 위쪽 좌표 x y, 기준 3x3 격자를 90도 회전하는 함수
# 이때 중심 좌표는 x + 1, y + 1 이 되겠지
# 이 함수를 쓰려면 전체 for문 돌릴때, 중심좌표 기준으로 돌리면 안됨...
 -> 전체 코드 수정해야함
def rotate_90(board, x, y):
    new_board = [[0] * 5 for _ in range(5)]

    for i in range(5):
        for j in range(5):
            # new_board[x + i]
            if i <= x + 1 and i >= x - 1 and j <= y + 1 and j >= y - 1:
                new_x = y
                new_y = 3-i-1
                new_board[new_x][new_y] = board[i][j]
            else:
                new_board[i][j] = board[i][j]
    return new_board

180, 270도 회전은 90도 회전을 2번, 3번 반복하도록 만들었다.

# 회전 함수
# x, y 기준 3x3격자를 ang만큼 회전하는 함수
def rotate(ang, board, x, y):
    # new_board = [[0] * 5 for _ in range(5)]
    new_board = board
    num = ang_list.index(ang) +1
    for _ in range(num):
        new_board = rotate_90(new_board, x, y)

    return new_board

3. 유물 획득

이 문제를 풀면서 엄청 친근..? 한 느낌이 든다.

꽤나 자주 봤던 유형중 하나.

가장 비슷하다고 느낀 것은 프로그래머스의 퍼즐 찾기

• 서로 연결된 유물 조각을 찾음
• 유물의 가치를 더함
• 유물 조각을 제거한 후, 빈 상태로 리턴

유물 조각을 제거하고, 다시 새로운 조각을 채워넣을 때 좌표 우선순위가 있기 때문에 서로 연결된 유물조각의 좌표를 구하는 것을 우선으로 한다.

전형적인 bfs문제.

def bfs(x, y, visited, board):
    q = deque()
    piece = [[x, y]]
    q.append([x, y, board[x][y]])

    while q:
        x, y, value = q.popleft()
        visited[x][y] = 1

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

            # 움직인 칸이 격자 밖
            if not is_board(nx, ny): continue
            # 이미 방문한 경우
            if visited[nx][ny] == 1: continue
            # 시작 값과 동일한 유물 조각을 가진 칸
            if board[nx][ny] == value:
                visited[nx][ny] = 1         # 방문처리
                q.append([nx, ny, value])   # 다음 좌표 저장
                piece.append([nx, ny])      # 유물을 지우고 좌표를 새로 채워넣을 때 이용
    if len(piece) < 3:
        return []

    return piece
    
    # 유물조각의 좌표를 출력하도록
def search_relic(board):
    visited = [[0] * 5 for _ in range(5)]
    pieces = []      # 유물 조각이 존재하는 좌표, 빈칸을 채울때 이용
    for i in range(5):
        for j in range(5):
            if visited[i][j] == 1: continue
            pieces.append(bfs(i, j, visited, board))
    # 빈 리스트 삭제
    pieces = [value for value in pieces if value]
    # 이중리스트 풀기
    pieces = [value for sub in pieces for value in sub]
    return pieces
    
    # 유물획득
def get_relic(board):
    # 서로 연결된 유물 조각을 찾음 -> 유물의 가치를 더함 -> 유물조각 없앰 -> 빈상태로 리턴
    # 서로 연결된 유물 조각 찾음
    relics = search_relic(board)
    rel_value = len(relics)
    # 열이 작은 순, 행이 작은 순으로 정렬
    relics = sorted(relics, key = lambda x:(x[1], -x[0]))

    return rel_value, relics

여기서 주목할 점은, 정렬할 때 두 가지 기준으로 정렬 하는 것.

엄청엄청 자주 쓰이는데 막상 시험장 가면 너무 생각이 안나서 머리를 쥐어뜯고 난리도 아니였다..

이제 진짜 잘 쓰는 정렬 중 하나..

4. 가장 큰 가치를 획득하는 방법 찾기

최대 유물의 가치 > 회전 각도 최소 > 중심좌표 (열, 행) 최소

순으로 우선순위를 지정한다.

또 하나 실수한 곳이 여기.

테스트케이스 6번에서 에러가 난다면 이 부분이 잘 못 된거다.

너무 자연스럽게 중심좌표를 행, 열로 정렬해버리면 테케 6번에서 걸리게 된다.

주석으로 다 달아놓고 코드를 짜도 실수를 하니까 시험장에서는 더더 조심하기

이때, 어떤 방법으로도 유물 가치를 얻을 수 없다면 탐사를 종료할 수 있는 flag 장치를 넣어줘야한다.

나는 그때 모두 0을 반환하도록 설정함

def exploration():
    # 모든 중심좌표, 각도를 다 확인
    # 회전각도 가장 작은 방법 -> 열이 가장 작은 좌표 -> 행이 가장 작은 좌표를 선택
    # 획득 가치가 최대인 것을 저장

    # 회전할 중심좌표 선택 -> 회전 -> 유물획득 -> 유물 획득 가치, 회전각도, 중심좌표 (열,행), board 순으로 정렬 -> max를 선택
    candidate = []
    # 3x3 격자를 선택하므로 첫번째와 마지막 행,열은 선택하지 않음
    for i in range(1, 4):
        for j in range(1, 4):
            # 모든 각도 확인
            for ang in ang_list:
                new_board = rotate(ang, board, i, j)
                # print_board(new_board)
                rel_value, relics = get_relic(new_board)
                if rel_value == 0:
                    continue
                candidate.append([rel_value, ang, j,i, new_board,relics ])
                # input('---')
    candidate = sorted(candidate,reverse=True, key = lambda x: (x[0], -x[1], -x[2], -x[3]))
    # 회전
    if not candidate:
        return 0,0,0,0,0,0
    # 회전이 완료된 좌표를 리턴
    return candidate[0]

연쇄작용

탐사가 끝난 후, 유물조각의 좌표를 얻었다.

우선순위 대로 정렬을 해준 후, 차례대로 주어진 유물조각을 pop시켜서 넣어준다.

이미 한번 사용한 조각은 사용하지 않기 때문에 pop시키는게 편하다.

유물조각을 획득하고 채우고 획득하고 채우고를 더 이상 얻을 수 있는 유물조각이 없을 때까지 반복하기 때문에 while문을 사용한다.

# 유물조각 연쇄획득
def get_sequence_relic(relics, board):
    # 유물 조각 삭제 및 채움

    board = process_relic(relics, board)
    # 연쇄반응 -> 계속 유물 찾다가 끝나면 리턴
    rel_value = 1
    total = 0
    while True:
        if rel_value == 0:
            break
        rel_value, relics = get_relic(board)
        total += rel_value
        # 유물 조각 삭제 및 채움
        board = process_relic(relics, board)

    return board, total

전체 코드

• 회전할 때 중심 좌표 기준 말고, 가장 왼쪽/가장 위쪽 기준으로 하면 쉽다
• 문제에서 주어진 우선순위를 조심하자!

k, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(5)]
piece = list(map(int, input().split()))

ang_list = [90, 180, 270]
from collections import deque

# board 프린트 함수
def print_board(board):
    for i in board:
        print(i)

# x, y 기준 3x3 격자를 90도 회전하는 함수
def rotate_90(board, x, y):
    new_board = [[0] * 5 for _ in range(5)]

    for i in range(5):
        for j in range(5):
            # new_board[x + i]
            if i <= x + 1 and i >= x - 1 and j <= y + 1 and j >= y - 1:

                new_x = x + (j-y)
                new_y = y-(i-x)
                new_board[new_x][new_y] = board[i][j]
            else:
                new_board[i][j] = board[i][j]
    return new_board

# 회전 함수
# x, y 기준 3x3격자를 ang만큼 회전하는 함수
def rotate(ang, board, x, y):
    # new_board = [[0] * 5 for _ in range(5)]
    new_board = board
    num = ang_list.index(ang) +1
    for _ in range(num):
        new_board = rotate_90(new_board, x, y)


    return new_board

# 탐사 진행
def exploration():
    # 모든 중심좌표, 각도를 다 확인
    # 회전각도 가장 작은 방법 -> 열이 가장 작은 좌표 -> 행이 가장 작은 좌표를 선택
    # 획득 가치가 최대인 것을 저장

    # 회전할 중심좌표 선택 -> 회전 -> 유물획득 -> 유물 획득 가치, 회전각도, 중심좌표 (열,행), board 순으로 정렬 -> max를 선택
    candidate = []
    # 3x3 격자를 선택하므로 첫번째와 마지막 행,열은 선택하지 않음
    for i in range(1, 4):
        for j in range(1, 4):
            # 모든 각도 확인
            for ang in ang_list:
                new_board = rotate(ang, board, i, j)
                # print_board(new_board)
                rel_value, relics = get_relic(new_board)
                if rel_value == 0:
                    continue
                candidate.append([rel_value, ang, j,i, new_board,relics ])
                # input('---')
    candidate = sorted(candidate,reverse=True, key = lambda x: (x[0], -x[1], -x[2], -x[3]))
    # 회전
    if not candidate:
        return 0,0,0,0,0,0
    # 회전이 완료된 좌표를 리턴
    return candidate[0]

# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 격자 내부 확인 함수
def is_board(x, y):
    return 0<= x < 5 and 0 <= y < 5

def bfs(x, y, visited, board):
    q = deque()
    piece = [[x, y]]
    q.append([x, y, board[x][y]])

    while q:
        x, y, value = q.popleft()
        visited[x][y] = 1

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

            # 움직인 칸이 격자 밖
            if not is_board(nx, ny): continue
            # 이미 방문한 경우
            if visited[nx][ny] == 1: continue
            # 시작 값과 동일한 유물 조각을 가진 칸
            if board[nx][ny] == value:
                visited[nx][ny] = 1         # 방문처리
                q.append([nx, ny, value])   # 다음 좌표 저장
                piece.append([nx, ny])      # 유물을 지우고 좌표를 새로 채워넣을 때 이용
    if len(piece) < 3:
        return []

    return piece

# 유물조각의 좌표를 출력하도록
def search_relic(board):
    visited = [[0] * 5 for _ in range(5)]
    pieces = []      # 유물 조각이 존재하는 좌표, 빈칸을 채울때 이용
    for i in range(5):
        for j in range(5):
            if visited[i][j] == 1: continue
            pieces.append(bfs(i, j, visited, board))
    # 빈 리스트 삭제
    pieces = [value for value in pieces if value]
    # 이중리스트 풀기
    pieces = [value for sub in pieces for value in sub]
    return pieces
# 유물획득
def get_relic(board):
    # 서로 연결된 유물 조각을 찾음 -> 유물의 가치를 더함 -> 유물조각 없앰 -> 빈상태로 리턴
    # 서로 연결된 유물 조각 찾음
    relics = search_relic(board)
    rel_value = len(relics)
    # 열이 작은 순, 행이 작은 순으로 정렬
    relics = sorted(relics, key = lambda x:(x[1], -x[0]))

    return rel_value, relics

# 유물 조각 삭제 및 채움
def process_relic(relics, board):
    # 유물조각 들을 삭제, 새로운 좌표 넣기
    for idx, [i, j] in enumerate(relics):
        board[i][j] = piece.pop(0)
    return board

# 유물조각 연쇄획득
def get_sequence_relic(relics, board):
    # 유물 조각 삭제 및 채움

    board = process_relic(relics, board)
    # 연쇄반응 -> 계속 유물 찾다가 끝나면 리턴
    rel_value = 1
    total = 0
    while True:
        if rel_value == 0:
            break
        rel_value, relics = get_relic(board)
        total += rel_value
        # 유물 조각 삭제 및 채움
        board = process_relic(relics, board)


    return board, total

result = []
# k 턴 움직임
for _ in range(k):
    # 탐사진행
    value, angle, x, y, board, relics = exploration()
    if board == 0:
        break

    # 유물조각 연쇄획득
    board, sequence_value = get_sequence_relic(relics, board)
    value += sequence_value
    result.append(str(value))
    # 유물가치 총합 출력
result = ' '.join(result)
print(result)