https://www.acmicpc.net/problem/20061
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.
이하 생략
행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.
블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.
입력
첫째 줄에 블록을 놓은 횟수 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)에 놓은 경우
블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.
출력
첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.
둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.
예제 입력 1
1
1 1 1
예제 출력 1
0
2
<그림 3>과 같다.
예제 입력 6
7
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3
2 0 0
3 2 0
예제 출력 6
1
18
<그림 10>과 같다.
예제 입력 7
8
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3
2 0 0
3 2 0
3 1 2
예제 출력 7
2
15
<그림 13>과 같다.
코드
# 20061 모노미노도미노 2
# t 모양: ㅇ, ㅡ, ㅣ
def blue_insert(t, x):
c_idx = 0
r = x
if t == 1:
while blue[r][c_idx] == 0 and c_idx < 5:
c_idx += 1
if blue[r][c_idx] == 1:
c_idx -= 1
elif t == 2:
while blue[r][c_idx] == 0 and blue[r][c_idx + 1] == 0 and c_idx < 4:
c_idx += 1
if blue[r][c_idx] == 1 or blue[r][c_idx + 1] == 1:
c_idx -= 1
blue[r][c_idx + 1] = 1
elif t == 3:
while blue[r][c_idx] == 0 and blue[r + 1][c_idx] == 0 and c_idx < 5:
c_idx += 1
if blue[r][c_idx] == 1 or blue[r + 1][c_idx] == 1:
c_idx -= 1
blue[r + 1][c_idx] = 1
blue[r][c_idx] = 1
def get_blue_score():
cnt = 0
for c in range(2, 6):
for r in range(4):
if blue[r][c] == 0:
break
else:
cnt += 1
for r in range(4):
blue[r][c] = 0
# 터진 것 채우기
for temp_c in range(c, 0, -1):
for r in range(4):
blue[r][temp_c] = blue[r][temp_c - 1]
blue[r][temp_c - 1] = 0
return cnt
def push_blue():
global blue
cur_c = -1
for c in range(2):
for r in range(4):
if blue[r][c] == 1:
cur_c = c
break
if cur_c != -1:
break
# 밝은 곳에 숫자가 없으면 return
if cur_c == -1:
return
temp_blue = [[0] * 6 for _ in range(4)]
push_num = 0
# 두 칸 밀기
if cur_c == 0:
push_num = 2
# 한 칸 밀기
elif cur_c == 1:
push_num = 1
for c in range(2, 6):
for r in range(4):
temp_blue[r][c] = blue[r][c - push_num]
blue = [temp[:] for temp in temp_blue]
# t 모양: ㅇ, ㅡ, ㅣ
def green_insert(t, y):
r_idx = 0
c = y
if t == 1:
while green[r_idx][c] == 0 and r_idx < 5:
r_idx += 1
if green[r_idx][c] == 1:
r_idx -= 1
elif t == 2:
while green[r_idx][c] == 0 and green[r_idx][c + 1] == 0 and r_idx < 5:
r_idx += 1
if green[r_idx][c] == 1 or green[r_idx][c + 1] == 1:
r_idx -= 1
green[r_idx][c + 1] = 1
elif t == 3:
while green[r_idx][c] == 0 and green[r_idx + 1][c] == 0 and r_idx < 4:
r_idx += 1
if green[r_idx][c] == 1 or green[r_idx + 1][c] == 1:
r_idx -= 1
green[r_idx + 1][c] = 1
green[r_idx][c] = 1
def get_green_score():
cnt = 0
for r in range(2, 6):
for c in range(4):
if green[r][c] == 0:
break
else:
cnt += 1
for c in range(4):
green[r][c] = 0
# 터진 것 채우기
for temp_r in range(r, 0, -1):
for c in range(4):
green[temp_r][c] = green[temp_r - 1][c]
green[temp_r - 1][c] = 0
return cnt
def push_green():
global green
cur_r = -1
for r in range(2):
for c in range(4):
if green[r][c] == 1:
cur_r = r
break
if cur_r != -1:
break
# 밝은 곳에 숫자가 없으면 return
if cur_r == -1:
return
temp_green = [[0] * 4 for _ in range(6)]
push_num = 0
# 두 칸 밀기
if cur_r == 0:
push_num = 2
# 한 칸 밀기
elif cur_r == 1:
push_num = 1
for r in range(2, 6):
for c in range(4):
temp_green[r][c] = green[r - push_num][c]
green = [temp[:] for temp in temp_green]
N = int(input())
blue = [[0] * 6 for _ in range(4)]
green = [[0] * 4 for _ in range(6)]
score = 0
for _ in range(N):
t, x, y = map(int, input().split())
# Blue에 블록 넣기
blue_insert(t, x)
# 점수 획득
score += get_blue_score()
# 연한 칸 블록 있으면 밀기
push_blue()
# Green에 블록 넣기
green_insert(t, y)
# 점수 획득
score += get_green_score()
# 연한 칸 블록 있으면 밀기
push_green()
block_cnt = 0
# 파란색 타일 갯수 세기
for r in range(4):
for c in range(2, 6):
if blue[r][c] == 1:
block_cnt += 1
# 초록색 타일 갯수 세기
for r in range(2, 6):
for c in range(4):
if green[r][c] == 1:
block_cnt += 1
print(score)
print(block_cnt)
틀린 부분
점수를 획득하고 나서, 터진 행/열의 위쪽/왼쪽에 있는 블록들을 땡겨오는 작업을 하지 않아 제출 직후 틀렸습니다. 를 볼 수 있었다.
틀린 예제 입력
4
2 3 0
2 3 0
2 1 0
2 1 2
위의 항목만 고친 뒤 정답을 맞출 수 있었다.
삼성 기출문제를 슥 훑어보기도 했고, 구현/시뮬레이션 알고리즘을 반복해서 풀다보니, 점점 구현 능력이 늘고 소요 시간이 줄어들고 있다.
효율적으로 함수를 만들어 푸는 스킬도 늘어나고 있는 것 같다.
화이팅!!
