1. 문제

---

모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.

이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.

블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.

여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.

다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.

초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.

여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.

초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.

위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.

여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.

크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.

파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.

<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 사라진 행의 위에 있는 블록이 아래로 한 칸씩 내려와야 한다. 이동한 후의 상태는 <그림 13>과 같다.

행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.

블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.

제한 사항

1 초 (추가 시간 없음)
메모리 : 512 MB

입력

첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.

둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.

• t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
• t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
• t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우

블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.

출력

첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.

둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.

- 키워드

• 단방향 BFS로 풀어보자.
• 룰을 제대로 이해하고 풀어야 실수를 없앨 수 있다.

2. 풀이

---

아마 문제가 너무 길어서 푸는 것을 포기할 사람이 있을정도로 문제가 엄청 길다.
(실제로도 타 문제 대비 제출수가 적은 편이다.)

하지만, 요점을 말하자면 다음과 같다.

1. 테트리스를 아래 오른쪽으로 떨어지는 것을 구현하면 된다.
2. 1줄이 꽉차면 그 줄을 지우고 1점을 추가한다.
3. 만일, 블럭이 4칸을 초과한다면 게임오버가 아니라 맨 밑에서부터 1줄을 땡긴다. (최대 2줄)
   - 이 때 줄을 땡겨도 점수는 오르지 않는다.
   

우리가 구현해야 할 것은 다음과 같을 것이다.

1. 초록색, 파란색에 규칙에 따른 블럭 이동
2. 초록색, 파란색 점수 책정법
3. 초록색, 파란색 초과시 블럭 땡기기

이렇게 구현하기만 하면,

블럭을 순서대로 입력 받을 것이다.

다음 테스트 케이스를 살펴보자.

8
3 0 0
3 0 1
3 0 2
3 0 3
2 0 0
2 1 0
2 2 0
2 3 0

본 풀이에서는 로직을 다음과 같이 구현했다.

1. 블록이 이동할 수 있는 위치까지 이동시킨다.
2. 점수 휙득 조건에 만족하는 줄이 있는지 체크한다.
   • 있다면 그 줄을 제거하고 그 위로부터 5줄을 땡겨온다.
3. 4칸보다 초과하여 놓여진 블록이 있는지 체크한다.
   • 있다면 맨 밑줄 서부터 5줄을 땡긴다 ( 최대 2칸 초과할 수 있으므로 2번까지 실행한다. )

다음과 같은 게임 보드판을 만든다.

board = [[0]*10 for _ in range(4)] + [[0]*4 for _ in range(6)]
for i in range(4):
	board[i].append(1)
board.append([1,1,1,1])

맨 끝에 1을 추가해준 이유는 indexerror 방지 편의성과 바닥을 뜻하기 때문이다.

첫 번째 블록을 떨어트린다.

def move_blue(t,row,col):
	check = deque()
	if t == 1:
		check.append([row,col])
	elif t == 2:
		check.append([row,col+1])
	else:
		check.append([row,col])
		check.append([row+1,col])

	while check:
		next_check = deque()
		while check:
			r,c = check.popleft()
			if board[r][c+1] == 0:
				next_check.append([r,c+1])
			else:
				if t == 1:
					board[r][c] = 1
				elif t == 2:
					board[r][c] = 1
					board[r][c-1] = 1
				else:
					board[r][c] = 1
					if r == row:
						board[r+1][c] = 1
					else:
						board[r-1][c] = 1
				next_check = []
				break
		check = next_check

def move_green(t,row,col):
	check = deque()
	if t == 1:
		check.append([row,col])
	elif t == 2:
		check.append([row,col])
		check.append([row,col+1])
	else:
		check.append([row+1,col])

	while check:
		next_check = deque()
		while check:
			r,c = check.popleft()
			if board[r+1][c] == 0:
				next_check.append([r+1,c])
			else:
				if t == 1:
					board[r][c] = 1
				elif t == 2:
					board[r][c] = 1
					if c == col:
						board[r][c+1] = 1
					else:
						board[r][c-1] = 1
				else:
					board[r-1][c] = 1
					board[r][c] = 1
				next_check = []
				break
		check = next_check

점수를 휙득할 수 없고, 4칸을 초과하지 않으므로 세 번째 까지 떨어트린다.

네 번째 블록을 떨어트리면 초록색 게임판에서 2점을 휙득한다.

위에서부터 1줄을 지우고 점수를 휙득한 뒤, 5줄을 당긴다.

def score_green(answer):
	rows = deque()
	for i in range(4):
		if board[6+i][0] + board[6+i][1] + board[6+i][2] + board[6+i][3] == 4:
			rows.append(6+i)
	while rows:
		row = rows.popleft()
		answer[0] += 1
		for i in range(5):
			board[row-i][0] = board[row-1-i][0]
			board[row-i][1] = board[row-1-i][1]
			board[row-i][2] = board[row-1-i][2]
			board[row-i][3] = board[row-1-i][3]

위에는 아무런 블럭이 없으므로 줄이 지워지기만 한다.

그리고 그 다음 줄 역시 점수를 휙득하고 위로 5줄을 당긴다.

끝나고, 초과하는 블록이 있는지 찾는다.

지금은 초과하는 블록이 없으므로, 다섯 번째 블록을 떨어트린다.

이번에는 점수를 휙득하는 경우는 없지만, 파란색 보드에서 2칸을 초과해버린다.

파란색 보드 바닥에서 위로 5줄을 당긴다.

def check_blue():
	check = 0
	for i in range(2):
		check += max(board[0][4+i],board[1][4+i],board[2][4+i],board[3][4+i])
	for _ in range(check):
		for i in range(1,5):
			board[0][-1-i] = board[0][-1-i-1]
			board[1][-1-i] = board[1][-1-i-1]
			board[2][-1-i] = board[2][-1-i-1]
			board[3][-1-i] = board[3][-1-i-1]
	for i in range(4):
		board[i][4] = board[i][5] = 0

아직 1칸을 더 초과하므로 다시 한 번 더 당긴다.

그 다음 여섯 번째 ~ 여덟 번째 블록을 떨어트린다.

마지막 블록을 떨어트렸을 때 파란색 보드에서 2점을 추가한다.

위에서부터 차례대로 5칸을 땡겨온다.

def score_blue(answer):
	cols = deque()
	for i in range(4):
		if board[0][6+i] + board[1][6+i] + board[2][6+i] + board[3][6+i] == 4:
			cols.append(6+i)
	while cols:
		col = cols.popleft()
		answer[0] += 1
		for i in range(5):
			board[0][col-i] = board[0][col-1-i]
			board[1][col-i] = board[1][col-1-i] 
			board[2][col-i] = board[2][col-1-i]
			board[3][col-i] = board[3][col-1-i]

점수를 출력하고

모든 블록을 다 떨어트리고 초록색 보드와 파란색 보드에 남아있는 블록을 출력한다.

해당 테스트케이스의 정답은
4
10
이다.

3. 소스코드

---

import sys
from collections import deque
input = sys.stdin.readline

board = [[0]*10 for _ in range(4)] + [[0]*4 for _ in range(6)]
for i in range(4):
	board[i].append(1)
board.append([1,1,1,1])

def check_blue():
	check = 0
	for i in range(2):
		check += max(board[0][4+i],board[1][4+i],board[2][4+i],board[3][4+i])
	for _ in range(check):
		for i in range(1,5):
			board[0][-1-i] = board[0][-1-i-1]
			board[1][-1-i] = board[1][-1-i-1]
			board[2][-1-i] = board[2][-1-i-1]
			board[3][-1-i] = board[3][-1-i-1]
	for i in range(4):
		board[i][4] = board[i][5] = 0

def check_green():
	check = 0
	for i in range(2):
		check += max(board[4+i][0],board[4+i][1],board[4+i][2],board[4+i][3])
	for _ in range(check):
		for i in range(1,5):
			board[-1-i][0] = board[-1-i-1][0]
			board[-1-i][1] = board[-1-i-1][1]
			board[-1-i][2] = board[-1-i-1][2]
			board[-1-i][3] = board[-1-i-1][3]
	for i in range(2):
		board[4+i][0] = board[4+i][1] = board[4+i][2] = board[4+i][3] = 0

def score_blue(answer):
	cols = deque()
	for i in range(4):
		if board[0][6+i] + board[1][6+i] + board[2][6+i] + board[3][6+i] == 4:
			cols.append(6+i)
	while cols:
		col = cols.popleft()
		answer[0] += 1
		for i in range(5):
			board[0][col-i] = board[0][col-1-i]
			board[1][col-i] = board[1][col-1-i] 
			board[2][col-i] = board[2][col-1-i]
			board[3][col-i] = board[3][col-1-i]

def score_green(answer):
	rows = deque()
	for i in range(4):
		if board[6+i][0] + board[6+i][1] + board[6+i][2] + board[6+i][3] == 4:
			rows.append(6+i)
	while rows:
		row = rows.popleft()
		answer[0] += 1
		for i in range(5):
			board[row-i][0] = board[row-1-i][0]
			board[row-i][1] = board[row-1-i][1]
			board[row-i][2] = board[row-1-i][2]
			board[row-i][3] = board[row-1-i][3]

def move_blue(t,row,col):
	check = deque()
	if t == 1:
		check.append([row,col])
	elif t == 2:
		check.append([row,col+1])
	else:
		check.append([row,col])
		check.append([row+1,col])

	while check:
		next_check = deque()
		while check:
			r,c = check.popleft()
			if board[r][c+1] == 0:
				next_check.append([r,c+1])
			else:
				if t == 1:
					board[r][c] = 1
				elif t == 2:
					board[r][c] = 1
					board[r][c-1] = 1
				else:
					board[r][c] = 1
					if r == row:
						board[r+1][c] = 1
					else:
						board[r-1][c] = 1
				next_check = []
				break
		check = next_check

def move_green(t,row,col):
	check = deque()
	if t == 1:
		check.append([row,col])
	elif t == 2:
		check.append([row,col])
		check.append([row,col+1])
	else:
		check.append([row+1,col])

	while check:
		next_check = deque()
		while check:
			r,c = check.popleft()
			if board[r+1][c] == 0:
				next_check.append([r+1,c])
			else:
				if t == 1:
					board[r][c] = 1
				elif t == 2:
					board[r][c] = 1
					if c == col:
						board[r][c+1] = 1
					else:
						board[r][c-1] = 1
				else:
					board[r-1][c] = 1
					board[r][c] = 1
				next_check = []
				break
		check = next_check

def solution(N,block):
	answer = [0]
	for b in block:
		t,row,col = b
		move_green(t,row,col)
		move_blue(t,row,col)
		score_green(answer)
		score_blue(answer)
		check_green()
		check_blue()
	print(answer[0])
	cnt = 0
	for row in range(4):
		for col in range(6,10):
			if board[row][col] == 1:
				cnt += 1
	for row in range(6,10):
		for col in range(4):
			if board[row][col] == 1:
				cnt += 1
	print(cnt)


if __name__ == "__main__":
	N = int(input())
	block = []
	for _ in range(N):
		block.append(list(map(int,input().split())))
	solution(N,block)

4. 후기

---

세부적인 기능 자체는 어렵진 않지만, 모두 합치려고하니 어려운 부분이 있다.

뭣보다 문법적인 부분에서 실수를 해서 아쉬웠던 문제다.