https://www.acmicpc.net/problem/21611
"""
"""
"""
0. 격자판 배치
1. 구슬 파괴
2. 2차원 배열을 1차원 배열로 변환
3. 구슬 이동
4. 구슬 폭발
-> 3, 4의 과정을 더 이상 구슬이 폭발하지 않을 때(연속하는 구슬의 번호가 4개 미만)까지 반복
5. 구슬 변화
6. 1차원 배열을 2차원 배열로 다시 변환
-> 1 ~ 6의 과정을 M만큼 반복
7. 폭발한 구슬을 점수화 해서 출력
"""
N, M = map(int, input().split()) # N:격자판 크기, M:마법 횟수
pan = [ list(map(int, input().split())) for _ in range(N) ] # 격자판
magic = [ list(map(int, input().split())) for _ in range(M) ] # 블리자드의 마법
s_x, s_y = N//2, N//2 # 상어의 좌표
pan[s_x][s_y] = -1 # 상어 : -1로 표시 (빈칸 : 0, 구슬 : 1, 2, 3)
answer = 0
dx = [-1, 1, 0, 0] # 상, 하, 좌, 우
dy = [0, 0, -1, 1]
def bead_destroy(d, s): # 구슬을 파괴하는 함수
x, y = s_x, s_y
for _ in range(s):
mx = x + dx[d]
my = y + dy[d]
pan[mx][my] = 0
x, y = mx, my
def bead_2d_1d(arr_2d): # 2차원 배열을 1차원 배열로 변환
d_dx, d_dy = [0, 1, 0, -1], [-1, 0, 1, 0]
visited = [ [False] * N for _ in range(N) ]
arr_1d = []
x, y = s_x, s_y
dir = -1
while True:
visited[x][y] = True
arr_1d.append(arr_2d[x][y])
if x == 0 and y == 0:
break
md = (dir + 1) % 4
mx = x + d_dx[md]
my = y + d_dy[md]
if visited[mx][my] == True: # 만약 방문한 곳이라면 방향을 꺾지말고 이전 방향 그대로 직진
md = dir
mx = x + d_dx[md]
my = y + d_dy[md]
x, y, dir = mx, my, md
return arr_1d
def bead_move(arr): # 빈자리를 채우는 구슬의 이동
tmp = []
for x in arr:
if x > 0:
tmp.append(x)
return tmp
def bead_bomb(arr): # 구슬의 폭발 함수 + 폭발한 구슬의 개수에 대한 점수 계산
global answer
flag = False # 구슬이 폭발한다면 True, 폭발하지 않았다면 False
n = len(arr)
num = 0 # 연속하는 구슬의 번호
cnt = 1 # 연속하는 구슬의 개수
for i in range(n-1):
if arr[i] == arr[i+1]:
num = arr[i]
cnt += 1
else:
if cnt >= 4:
arr[i-cnt+1:i+1] = [0]*cnt # 구슬 폭발
answer += (num * cnt) # 구슬 폭발에 따른 점수 계산
flag = True
cnt = 1
if cnt >= 4:
arr[n-cnt+1:n+1] = [0]*cnt
answer += (num * cnt)
flag = True
return arr, flag
def bead_motivation(arr): # 구슬의 변화를 시켜주는 함수
tmp = []
n = len(arr)
cnt = 1
if not arr: # 만약 빈 구슬만 들어오는 경우 빈 배열로 반환
return tmp
for i in range(n-1): # 1 ~ n-1까지 구슬의 변화를 시켜줌
if arr[i] == arr[i+1]:
cnt += 1
else:
tmp.append(cnt)
tmp.append(arr[i])
cnt = 1
if cnt >= 2: # 만약 n-2에서 cnt += 1만 하고 끝나는 경우 마지막 배열 원소를 세기위해 이렇게 반복문 구성
tmp.append(cnt)
tmp.append(arr[n-1])
else: #
tmp.append(cnt)
tmp.append(arr[n-1])
return tmp
def bead_1d_2d(arr_1d): # 1차원 배열을 2차원 배열로 변환
# 만약, 구슬이 칸의 수보다 많아 칸에 들어가지 못하는 경우 그러한 구슬은 사라진다 -> 구현하기 위해 범위 제한
n = N**2-1 if len(arr_1d) > N**2-1 else len(arr_1d)
d_dx, d_dy = [0, 1, 0, -1], [-1, 0, 1, 0]
arr_2d = [ [0] * N for _ in range(N) ]
visited = [ [False] * N for _ in range(N) ]
arr_2d[s_x][s_y] = -1
x, y = s_x, s_y
dir = -1
for i in range(n):
visited[x][y] = True
md = (dir + 1) % 4
mx = x + d_dx[md]
my = y + d_dy[md]
if visited[mx][my] == True:
md = dir
mx = x + d_dx[md]
my = y + d_dy[md]
arr_2d[mx][my] = arr_1d[i]
x, y, dir = mx, my, md
return arr_2d
for d, s in magic:
bead_destroy(d-1, s) # 구슬 파괴
pan_1d = bead_2d_1d(pan) # 2차원 배열 -> 1차원 배열
# print(pan_1d)
pan_1d = bead_move(pan_1d) # 빈자리를 채우기 위한 구슬의 이동
# print(pan_1d)
while True:
pan_1d, flag = bead_bomb(pan_1d) # 구슬의 폭발
if flag == True: # 폭발한 곳은 0으로 채웠기 때문에 다시 구슬의 이동 필요
pan_1d = bead_move(pan_1d) # 빈자리를 채우기 위한 구슬의 이동
else: # 폭발하지 않았다면 더 이상 폭발할 곳이 없는것을 의미하므로 반복문 탈출
break
# print(pan_1d)
pan_1d = bead_motivation(pan_1d) # 구슬의 변화
# print(pan_1d)
pan = bead_1d_2d(pan_1d) # 1차원 배열로 변환했던 것을 다시 2차원 배열로 변환
# for i in pan:
# print(i)
print(answer)
구슬 변화 부분에서 빈 구슬만 들어오는 경우 처리를 따로 해주어야함 (히든 케이스 고려)
3 1
0 0 0
0 0 0
0 0 0
1 1
구슬이 폭발할 때 반복문 구성에서 마지막 인덱스 까지 깔끔하게 처리해야 함
if cnt >= 4:
arr[n-cnt+1:n+1] = [0]cnt
answer += (num cnt)
flag = True
★ 2차원 배열을 1차원 배열로, 1차원 배열을 2차원 배열로 변환 시키는 아이디어 생각