기준 블록을 왼쪽 위에서 오른쪽 아래 순서로 골라서 블록 그룹을 찾으므로 현재 고른 블록이 기준 블록의 행이 가장 크고 열이 가장 큰 것이다. 따라서 크기가 같고 무지개 블록의 수도 같은 경우는 갱신시켜 주어야 한다.
(1)에서 구한 블록 그룹을 모두 제거한다. 이 때 점수도 같이 구해준다.
제거 표시는 -2로 표시하고, 점수는 블록 그룹 내 블록의 수 제곱을 해준다.
중력 기능을 구현한다.
가장 아래 행에서부터 시작해서 하나하나의 요소들을 아래에 -2가 나타나지 않을때까지 당겨준다.
회전 기능을 구현한다.
matrix[i][j] = matrix[j][len(matrix[0])-1-i]
구현 순서에 맞추어서 전체 기능을 조합한다. 이 때, 최대 블록 그룹을 구했을 때, 그룹이 없거나 그룹 내 블록의 수가 1개인 경우에 게임을 종료시킨다.
소스 코드
import sys
from collections import deque
import copy
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
def bfs(matrix, startX, startY):
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
queue = deque([[startX, startY]])
block_color = matrix[startX][startY]
matrix[startX][startY] = -1
block_count = 1
rainbow = []
block = [[startX, startY]]
while queue:
x, y = queue.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx and nx < N and 0 <= ny and ny < N:
if matrix[nx][ny] == block_color or matrix[nx][ny] == 0:
queue.append([nx, ny])
block.append([nx, ny])
block_count += 1
if matrix[nx][ny] == 0:
rainbow.append([nx, ny])
matrix[nx][ny] = -1
for nx, ny in rainbow:
matrix[nx][ny] = 0
return block, block_count, len(rainbow)
def find_max_block(target):
matrix = copy.deepcopy(target)
max_block, max_block_count, max_rainbow = None, 0, 0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] > 0:
block, block_count, rb_len = bfs(matrix, i, j)
if max_block_count < block_count:
max_block, max_block_count, max_rainbow = block, block_count, rb_len
elif max_block_count == block_count:
if max_rainbow <= rb_len:
max_block, max_block_count, max_rainbow = block, block_count, rb_len
return max_block
def destroy(matrix, block):
for x, y in block:
matrix[x][y] = -2
def gravity(matrix):
for i in range(len(matrix)-2, -1, -1):
for j in range(len(matrix[0])):
index = i
if matrix[i][j] == -1:
continue
while index+1 != N and matrix[index+1][j] == -2:
matrix[index+1][j] = matrix[index][j]
matrix[index][j] = -2
index += 1
def rotate(matrix):
new_matrix = copy.deepcopy(matrix)
for i in range(len(matrix)):
for j in range(len(matrix[0])):
new_matrix[i][j] = matrix[j][len(matrix)-1-i]
return new_matrix
score = 0
while True:
block = find_max_block(matrix)
if block == None:
break
if len(block) <= 1:
break
score += (len(block) ** 2)
destroy(matrix, block)
gravity(matrix)
matrix = rotate(matrix)
gravity(matrix)
print(score)
이 때, 블록이 바닥에 닿지 않는다면, 해당 블록을 이동시켜주어야 하니 잠시 저장시켜 둔다.
바닥에 닿지 않는 블록이 있는 경우, 바닥에 닿지 않는 블록들을 몇칸 내려야 다른 블록에 충돌하는지 벽에 닿는지 검사하고, 해당 칸수만큼 블록 내 모든 미네랄들을 내려준다.
1-3번 과정을 반복한다.
소스 코드
import sys
from collections import deque
import copy
input = lambda: sys.stdin.readline().rstrip()
R, C = map(int, input().split())
matrix = [list(input()) for _ in range(R)]
N = int(input())
throws = map(int, input().split())
def bfs(matrix, sx, sy):
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
block = [[sx, sy]]
queue = deque([[sx, sy]])
matrix[sx][sy] = '.'
down = False if sx == R-1 else True
while queue:
sx, sy = queue.popleft()
for i in range(4):
nx, ny = sx + dx[i], sy + dy[i]
if nx >= 0 and nx < R and ny >= 0 and ny < C and \
matrix[nx][ny] == 'x':
down = False if nx == R-1 else down
block.append([nx, ny])
queue.append([nx, ny])
matrix[nx][ny] = '.'
return block, down
def movedown(matrix, block):
for x, y in block:
matrix[x][y] = '.'
movement_count = 0
# 몇칸 이동해야하는지 구함
for i in range(1, R):
for x, y in block:
if x+i+1 == R or matrix[x+i+1][y] == 'x':
movement_count = i
break
if movement_count != 0:
break
for x, y in block:
matrix[x+movement_count][y] = 'x'
def check(matrix):
target = None
cp_matrix = copy.deepcopy(matrix)
for i in range(len(cp_matrix)):
for j in range(len(cp_matrix[0])):
if cp_matrix[i][j] == 'x':
block, down = bfs(cp_matrix, i, j)
if down:
target = block
break
if target:
break
if target:
movedown(matrix, target)
left = True
for throw in throws:
if left:
for j in range(C):
if matrix[R-throw][j] == 'x':
matrix[R-throw][j] = '.'
break
else:
for j in range(C-1, -1, -1):
if matrix[R-throw][j] == 'x':
matrix[R-throw][j] = '.'
break
check(matrix)
left = not left
for m in matrix:
print("".join(m))
따라서, left의 행,열에서 시작해서 right의 행,열까지 순서대로 이동하면서 값을 넣어주면 된다.
left의 행일때는 left의 열~N열까지 단, left의 행과 right의 행이 같은 경우는 left의 열 ~ right의 열까지
left의 행 + 1 ~ right의 행 - 1 구간에서는 (1~N열)
right의 행에서는 1~right의 열까지
값을 넣어줄 때는 i행에서 i열까지는 i를 넣어주고, 이후에는 열에 맞추어서 넣어주면 된다.
소스 코드
def solution(n, left, right):
answer = []
sr, sc = (left // n)+1, (left % n)+1
er, ec = (right // n)+1, (right % n)+1
if sr == er:
for j in range(sc, ec+1):
if j <= sr:
answer.append(sr)
else:
answer.append(j)
return answer
else:
for j in range(sc, n+1):
if j <= sr:
answer.append(sr)
else:
answer.append(j)
for i in range(sr+1, er):
for j in range(1, n+1):
if j <= i:
answer.append(i)
else:
answer.append(j)
for j in range(1, ec+1):
if j <= er:
answer.append(er)
else:
answer.append(j)
return answer
현재 위치에 넴모를 넣을수 있으면 넣어보고, 넣을수 없으면 넣지 않고 다음 위치로 이동한다.
이 때, 넴모를 넣었는지 넣지 않았는지 확인하기 위한 격자판을 미리 만들어두고 넴모를 넣었을때 1, 넣지 않았을때 0으로 설정한다.
현재 위치 기준으로 왼쪽, 왼쪽위, 위에 넴모가 있는지 확인하고, 넴모가 모두 있으면 현재 위치엔 넣을수 없으므로 넣지 않고, 넴모가 한군데라도 없다면 현재 위치에 넣을 수 있으므로 넣는다.
넴모를 넣을때마다 정답을 하나씩 증가시켜서 마지막에 전체 경우의 수를 출력시켜 준다.
쉬운 문제인거 같은데 뭔가 많이 헤맸던것 같다.. 넴모의 위치를 처음에는 Set으로 했었는데.. 계속해서 시간초과에 걸려서 행렬로 바꾸었음, 그래도 시간초과에 걸려서 원래 현재 위치 기준으로 삽입할 수 있는지 체크하는걸 함수로 구현하였었는데, 함수에서 일반 비교식으로 바꾸니 시간 초과가 걸리지 않음.
소스 코드
import sys
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
block_set = set()
matrix = [[0] * (M+1) for _ in range(N+1)]
def solve(i, j):
answer = 0
if j > M:
i, j = i+1, 1
if i > N:
return 0
if matrix[i-1][j] == 0 or matrix[i][j-1] == 0 or matrix[i-1][j-1] == 0:
matrix[i][j] = 1
answer += (1 + solve(i, j+1))
matrix[i][j] = 0
answer += solve(i, j+1)
return answer
print(solve(1, 1) + 1)