꼭 알아야 할 코드:
1) 시계방향 90도 회전
output_arr = list(map(list, zip(*input_arr[::-1])))
2) 180도 회전
output_arr = [a[::-1] for a in input_arr[::-1]]
3) 270도 회전
output_arr = [x[::-1] for x in list(map(list, zip(*input_arr[::-1])))[::-1]]코드 실수 주의
1) sort할 때 행 번호 큰 순인데 작은 순으로 잘못 봄! 조건 잘 보기
2) 탐사 진행하고 최대 유물인 경우 찾았는데 그 때의 회전한 맵을 현재 maps에 적용 안했음
3) BFS 할 때 같은 유적끼리 연결된 덩어리 카운트 하려면, group 리스트에 BFS 하면서 방문한 좌표를 모두 모아서 그 길이를 세어서 그걸로 연결된 조각 개수를 처리해야 함!
from collections import deque
K, M = map(int, input().split())
maps = []
for i in range(5):
line = list(map(int, input().split()))
maps.append(line)
wall = list(map(int, input().split()))
wall_idx = 0
# 중심 좌표(x, y) 기준으로 3x3 행렬의 좌표 구하는 dx, dy
dx = [-1, -1, -1, 0, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 0, 1, -1, 0, 1]
def value_count(input_maps):
dx_2 = [1, 0, 0, -1]
dy_2 = [0, -1, 1, 0]
visited = [[False] * 5 for _ in range(5)]
total_cnt = 0
total_group = []
# 맵 전체 좌표 하나씩 돌면서 BFS 실행
for j in range(5):
for k in range(5):
start_x, start_y = j, k
# 이미 방문한 좌표라면 패스
if visited[start_x][start_y]:
continue
# (start_x, start_y)에서 시작하는 BFS 수행
visited[start_x][start_y] = True
q = deque()
q.append((start_x, start_y, input_maps[start_x][start_y]))
group = [(start_x, start_y)]
while q:
x, y, num = q.popleft()
for i in range(4):
nx, ny = x + dx_2[i], y + dy_2[i]
if 0 <= nx < 5 and 0 <= ny < 5 and not visited[nx][ny] and input_maps[nx][ny] == num:
q.append((nx, ny, num))
group.append((nx, ny))
visited[nx][ny] = True
# 찾은 유물 조각이 3개 이상 연결되어 있다면, 맵 안의 전체 유물에 추가
if len(group) >= 3:
total_cnt += len(group)
total_group.extend(group)
return total_cnt, total_group
def spin_arr(degree, input_arr):
if degree == 0: # 90도 회전
output_arr = list(map(list, zip(*input_arr[::-1])))
elif degree == 1: # 180도 회전
output_arr = [a[::-1] for a in input_arr[::-1]]
elif degree == 2: # 270도 회전
output_arr = [x[::-1] for x in list(map(list, zip(*input_arr[::-1])))[::-1]]
return output_arr
def tamsa():
max_val = -1
max_group = []
turned_maps = []
# 가능한 회전 중심 좌표 : 열이 작은 순서, 행이 작은 순서대로 탐색!
mid_list = [(1, 1), (2, 1), (3, 1), (1, 2), (2, 2), (3, 2), (1, 3), (2, 3), (3, 3)]
# 각도가 가장 작은 순으로 탐색
for d in range(3): # d = 0은 90도, d = 1은 180도, d = 2는 270도
for x, y in mid_list:
mini_3x3 = []
idx = 0
for i in range(3):
line = []
for j in range(3):
nx, ny = x + dx[idx], y + dy[idx]
line.append(maps[nx][ny])
idx += 1
mini_3x3.append(line)
# mini_3x3을 d도 돌리기
spined_arr = spin_arr(d, mini_3x3)
# spined_arr를 복사한 맵에 적용하기
copy_maps = [row[:] for row in maps]
idx = 0
for i in range(3):
for j in range(3):
nx, ny = x + dx[idx], y + dy[idx]
copy_maps[nx][ny] = spined_arr[i][j]
idx += 1
# 복사한 맵에 spined_arr가 적용된 상태에서 유물 1차 획득 가능한 가치 카운트
total_cnt, total_group = value_count(copy_maps)
if total_cnt > max_val:
max_val = total_cnt
max_group = total_group
turned_maps = [row[:] for row in copy_maps]
return max_val, max_group, turned_maps
# 전체 K번 턴 진행
for turn in range(K):
turn_val = 0
max_val, max_group, turned_maps = tamsa()
# 탐사 진행 과정에서 어떠한 유물도 획득 불가였다면 그 즉시 종료
if max_val <= 0:
break
# 해당 턴의 유물 가치 누적
turn_val += max_val
# 3x3 회전된 맵을 현재 맵에 적용
maps = [row[:] for row in turned_maps]
# 조각이 사라진 위치에 벽면 숫자를 순서대로 채워주기
max_group.sort(lambda x: [x[1], -x[0]]) # 1) 열 작은순, 2) 행 큰순으로 정렬하기!!!!!
for ax, ay in max_group:
maps[ax][ay] = wall[wall_idx]
wall_idx += 1
# 유물 연쇄 획득
total_cnt, total_group = value_count(maps)
# 더 이상 조각이 3개 이상 연결되지 않아 유물이 될 수 없을 때까지 반복
while total_cnt >= 3:
# 해당 턴의 유물 가치 누적
turn_val += total_cnt
# 조각이 사라진 위치에 벽면 숫자를 순서대로 채워주기
total_group.sort(lambda x: [x[1], -x[0]]) # 1) 열 작은순, 2) 행 큰순으로 정렬하기
for ax, ay in total_group:
maps[ax][ay] = wall[wall_idx]
wall_idx += 1
# 채운 후 다시 유물 카운트
total_cnt, total_group = value_count(maps)
# 이번 턴의 총 획득 유물 가치 출력
print(turn_val, end=" ")
