문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.
- 크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
- 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
- 격자에 중력이 작용한다.
- 격자가 90도 반시계 방향으로 회전한다.
- 다시 격자에 중력이 작용한다.
- 격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.
입력
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다
해결방법
- 크기가 가장 큰 블록 그룹을 찾는 함수 find()를 작성한다. 여기서 가장 큰 블록 그룹이 여러개이고, 무지개 블록의 수가 같은 경우를 꼼꼼히 따져 코드를 작성한다 ( 이 부분에서 실수가 가장 많이 나왔다.) 나의 경우, 각 변수에 비교대상이 되는 값들을 매번 저장했고, 가장 큰 블록 그룹이 바뀌는 경우 변수를 바로바로 갱신해줬다.
- 중력이 작용하는 함수를 작성한다.
- 90도 반시계 방향으로 회전하는 함수를 작성한다.
코드
from collections import deque
# 게임은 크기가 N×N인 격자에서 진행
n, m = map(int, input().split())
board = []
for _ in range(n):
board.append(list(map(int, input().split())))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 1. 크기가 가장 큰 블록 그룹을 찾는다.
def find(board):
# 여러 블록 그룹 중 가장 큰 블록 그룹의 크기
max_size = 0
# 가장 큰 블록 그룹의 번호
max_group = -1
# 가장 큰 블록 그룹이 가지고 있는 무지개 블록의 수
max_rainbow = 0
# 블록 그룹의 번호
count = 0
# bfs를 위한 큐
queue = deque([])
# 각 그룹 블록에 포함되는 좌표 저장
his = {}
#레인보우 블록의 좌표 저장
rainbow_loc = {}
#일반 블록의 좌표 저장
block_loc = {}
# 방문 배열 초기화
visit = [list(0 for _ in range(n)) for _ in range(n)]
for i in range(n):
for j in range(n):
# 블록 그룹의 크기
size = 1
# 블록 그룹에 포함된 레인보우 블록
rainbow = 0
# 일반 블록이라면
if 0 < board[i][j] <= m and visit[i][j] == 0:
visit[i][j] = 1
count += 1
queue.append([i, j])
color = board[i][j] # 시작하는 일반 블록의 색상 저장
his[count] = [[i, j]]
block_loc[count] = [[i, j]]
rainbow_loc[count] = []
while queue:
#print(queue)
r, c = queue.popleft()
#visit[r][c] = 1
# print("start", color, r, c, count)
for k in range(4):
nx = r + dx[k]
ny = c + dy[k]
if 0<=nx<n and 0<=ny<n and (board[nx][ny]==color or board[nx][ny]==0) and visit[nx][ny] == 0:
#print(color, nx, ny, count, board[nx][ny])
if board[nx][ny] == 0:
# print("chk")
rainbow += 1
rainbow_loc[count].append([nx, ny])
else:
block_loc[count].append([nx, ny])
his[count].append([nx, ny])
queue.append([nx, ny])
visit[nx][ny] = 1
size += 1
for x, y in rainbow_loc[count]:
visit[x][y] = 0
# print("count", count)
# for v in visit:
# print(v)
# print("")
block_loc[count].sort()
#print(max_size, size)
if max_size < size:
max_size = size
max_group = count
max_rainbow = rainbow
# 1.1. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹,
elif max_size == size:
if max_rainbow < rainbow:
max_size = size
max_group = count
max_rainbow = rainbow
# 1.2. 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을,
elif max_rainbow == rainbow:
# print(max_group, block_loc[max_group], count, block_loc[count])
if block_loc[max_group][0][0] < block_loc[count][0][0]:
max_size = size
max_group = count
max_rainbow = rainbow
# 1.3. 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
elif block_loc[max_group][0][0] == block_loc[count][0][0]:
if block_loc[max_group][0][1] < block_loc[count][0][1]:
max_size = size
max_group = count
max_rainbow = rainbow
#print(max_group)
#max_group이 -1이라면 블록 그룹이 없으므로 게임을 종료한다
# 2. 1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B**2점을 획득한다.
if max_group < 1 or max_size < 2:
return -1, board
for i in range(n):
for j in range(n):
if [i, j] in his[max_group]:
board[i][j] = 6 # 사라진 곳은 6으로 표시
return max_size**2, board
# 3. 격자에 중력이 작용한다.
# 중력 작용 함수 6 - 빈칸
def move(board):
for i in range(n):
for j in range(n-1, -1, -1):
#print(i, j)
if board[j][i] != 6 and board[j][i] != -1:
start = j
#print("s", start)
while 0<=start+1<n and board[start+1][i] == 6:
#print(start)
board[start+1][i] = board[start][i]
board[start][i] = 6
start += 1
return board
# 4. 격자가 90도 반시계 방향으로 회전한다.
def rotate(board):
result = []
for i in range(n-1, -1, -1):
temp = []
for j in range(0, n):
temp.append(board[j][i])
result.append(temp)
return result
# 5. 다시 격자에 중력이 작용한다.
# 격자에 중력이 작용하면 "검은색 블록을 제외한 모든 블록"이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.
# for b in board:
# print(b)
# print("")
ans = 0
while True:
s, b = find(board)
# print("그룹 확인 후 삭제")
# for bb in b:
# print(bb)
# print("", ans)
if s == -1:
break
ans += s
m_b = move(b)
r_b = rotate(m_b)
m_b = move(r_b)
board = m_b
# for mm in m_b:
# print(mm)
# print("")
print(ans)