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

문제링크

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

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

처음엔 BFS로 쉽게 할 것 같았는데

이상한 곳에 꽂혀서 8시간 동안 헤맨 문제...

(Flood Fill도 필요하다)

 

회전의 중심을 1, 1에서 시작하고

그 다음은 2, 1에서 시작하도록 코드를 짜는거 까진 좋았는데,

1,1을 중심으로 회전한 이후 board를 업데이트 하는게 아니라

기존 board에서 2,1을 중심으로 회전시켜야 한다.

board 업데이트는 유물을 찾았을 때만 업데이트 하도록!

안그러면 M-list의 값이 모자라 Index Error가 발생하더라🤣

 

rotate 부분은 

list(map(list, zip(*arr[::-1]))) 와 같이 사용 가능하다.

 

deepcopy를 쓰긴 했는데 

copied = [row[:] for row in original] 와 같이 
새로 할당하는 방법도 존재한다.
리스트를 새로 선언하는 부분에서 용량과 속도에 문제가 발생할 수도 있다.

 

shallow copy와 deep copy에 관한 내용도 추후 정리할 것!

 

from collections import deque
from copy import deepcopy

def rotate(sy, sx, cnt):
    result = deepcopy(board)
    for _ in range(cnt):
        tmp = result[sy + 0][sx + 2]
        result[sy + 0][sx + 2] = result[sy + 0][sx + 0]
        result[sy + 0][sx + 0] = result[sy + 2][sx + 0]
        result[sy + 2][sx + 0] = result[sy + 2][sx + 2]
        result[sy + 2][sx + 2] = tmp
        tmp = result[sy + 1][sx + 2]
        result[sy + 1][sx + 2] = result[sy + 0][sx + 1]
        result[sy + 0][sx + 1] = result[sy + 1][sx + 0]
        result[sy + 1][sx + 0] = result[sy + 2][sx + 1]
        result[sy + 2][sx + 1] = tmp
    return result

def cal_score(board): 
    score = 0
    # 방문여부 체크
    visit = [[False] * 5 for _ in range(5)]
    # BFS 방향
    dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
    
    for i in range(5):
        for j in range(5):
            if not visit[i][j]:
                dq, trace = deque([(i, j)]), deque([(i, j)])
                visit[i][j] = True
                while dq:
                    cur = dq.popleft()
                    for k in range(4):
                        ny, nx = cur[0]+dy[k], cur[1]+dx[k]
                        if 0<=ny<5 and 0<=nx<5 and visit[ny][nx] == False and board[ny][nx] == board[cur[0]][cur[1]]:
                            dq.append((ny, nx))
                            trace.append([ny, nx])
                            visit[ny][nx] = True
                if len(trace) >= 3:
                    score += len(trace)
                    while trace:
                        t = trace.popleft()
                        board[t[0]][t[1]] = 0
    return score

def fill(b, qq):
    for j in range(5):
        for i in range(4, -1, -1):
            if b[i][j] == 0:
                b[i][j] = qq.popleft()
    return b

K, M = map(int, input().split())
board = []
for i in range(5):
    board.append(list(map(int, input().split())))
M_list = list(map(int, input().split()))
M_list = deque(M_list)

for _ in range(K):
    maxScore = 0
    maxScoreBoard = None
    for cnt in range(1, 4):
        for j in range(3):
            for i in range(3):
                rotated = rotate(i, j, cnt)
                score = cal_score(rotated)
                if maxScore < score:
                    maxScore = score
                    maxScoreBoard = rotated
    if maxScoreBoard is None:
        break
    board = maxScoreBoard
    while True:
        board = fill(board, M_list)
        newScore = cal_score(board)
        if newScore == 0:
            break
        maxScore += newScore

    print(maxScore, end=" ")