JB의 이모저모
[BOJ 20061🥇2] 모노미노도미노 2 (Python) 본문
https://www.acmicpc.net/problem/20061
20061번: 모노미노도미노 2
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행,
www.acmicpc.net
문제
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.
<그림 1> 모노미노도미노 게임 보드
이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.
<그림 2> 모노미노도미노 게임에서 사용하는 블록
블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.
<그림 3>
여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.
<그림 4>
다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.
<그림 5>
초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.
<그림 6>
여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.
<그림 7>
초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.
<그림 8>
위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.
<그림 9>
여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.
<그림 10>
크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.
<그림 11>
파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.
<그림 12>
<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 사라진 행의 위에 있는 블록이 아래로 한 칸씩 내려와야 한다. 이동한 후의 상태는 <그림 13>과 같다.
<그림 13>
행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.
블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.
입력
첫째 줄에 블록을 놓은 횟수 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>과 같다.
예제 입력 2
2
1 1 1
2 3 0예제 출력 2
0
6<그림 4>와 같다.
예제 입력 3
4
1 1 1
2 3 0
3 2 2
3 2 3예제 출력 3
1
10<그림 6>과 같다.
예제 입력 4
5
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3예제 출력 4
1
12<그림 8>과 같다.
예제 입력 5
6
1 1 1
2 3 0
3 2 2
3 2 3
3 1 3
2 0 0예제 출력 5
1
16<그림 9>와 같다.
예제 입력 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
⭕ CODE
def drop_green(t, y):
# 가장 바닥 인덱스는 5이므로 6을 지정
x = 6
# 모양이 네모 한칸이라면
if t == 1:
# 위에 인덱스 부터 조사하여
for i in range(6):
# 1을 만나면 그 높이 인덱스 x를 i로 지정
if green[i][y] == 1:
x = i
break
# 1이 나온 바로 위를 1로 만들어 준다.
# 즉 떨어트려주었다.
# 만약 인덱스 5 즉 바닥까지 1이 없으면 x = 6 이므로 바닥에 1이 생성됨
green[x - 1][y] = 1
# 위로 길쭉한 모양
elif t == 3:
for i in range(6):
if green[i][y] == 1:
x = i
break
# 만나는 지점의 바로 위와 그 위를 1로 만들어 주어야한다.
green[x - 1][y] = 1
green[x - 2][y] = 1
# 옆으로 길쭉한 모양
elif t == 2:
for i in range(6):
# 옆으로 기므로 y축에서 만나거나 혹은 y+1에서 먼저 만나는 x축의 높이를 구해줌
if green[i][y] == 1 or green[i][y + 1] == 1:
x = i
break
# 만나는 지점의 바로위의 y와 y+1 좌표를 1로 지정
green[x - 1][y] = 1
green[x - 1][y + 1] = 1
# 원래는 옆으로 미는거지만 떨어트리는 모양으로 바꾸었기에
# x,y좌표에 변화가 생긴다.
def drop_blue(t, x):
# 바닥을 위한 new_x 좌표
new_x = 6
# 원래 x좌표가 주어지지만 돌리면 그것이 y좌표가 되므로
# new_y 좌표는 3-x로 지정
new_y = 3 - x
# 녹색 떨어트리는 행동과 동일
# 다만 t == 2 일때 원래는 옆으로 긴 모양이지만
# 돌리면서 세로로 긴모양이 되고
# t == 3 일 때 세로로 긴 모양에서 가로로 긴 모양으로 바뀐다.
if t == 1:
for i in range(6):
if blue[i][new_y] == 1:
new_x = i
break
blue[new_x - 1][new_y] = 1
elif t == 2:
for i in range(6):
if blue[i][new_y] == 1:
new_x = i
break
blue[new_x - 1][new_y] = 1
blue[new_x - 2][new_y] = 1
elif t == 3:
for i in range(6):
if blue[i][new_y] or blue[i][new_y - 1] == 1:
new_x = i
break
blue[new_x - 1][new_y] = 1
blue[new_x - 1][new_y - 1] = 1
# 제거함수
def remove(arr, i):
# 지워야 하는 배열 arr -> green or blue
# 지워야 하는 높이 인덱스 x값 i
for a in range(i, 0, -1):
for b in range(4):
# 한칸씩 떨어트려준다.
arr[a][b] = arr[a - 1][b]
# 맨 윗부분은 아직 안바꿨다.
# 전부 0으로 바꾸어주어야한다.
for j in range(4):
arr[0][j] = 0
n = int(input())
# 녹색 부분 파란 부분
# 파란 부분도 돌려서 녹색과 마찬가지로 떨어트릴거다
green = [[0] * 4 for _ in range(6)]
blue = [[0] * 4 for _ in range(6)]
# 점수 result
result = 0
for _ in range(n):
# t : 블록 모양
# x,y는 좌표
t, x, y = map(int, input().split())
# 녹색 떨어트리는 drop_green 함수
# 떨어트리는 모양 t와 x축은 의미가 없으므로 y축을 사용
drop_green(t, y)
# 파란색 떨어트리는 drop_blue 함수
# 떨어트리는 모양 t와 x만 매개변수로 사용
drop_blue(t, x)
# 떨어트린 후
# 한 높이에 대해서 모두 1이라면
# 삭제해야한다.
for i in range(2, 6):
g_cnt = 0
b_cnt = 0
for j in range(4):
if green[i][j] == 1:
g_cnt += 1
if blue[i][j] == 1:
b_cnt += 1
# 한줄에 1이 4개라면
if g_cnt == 4:
# green 배열의 i높이를 삭제해야한다.
remove(green, i)
# 삭제했으므로 점수 1점 추가
result += 1
# blue도 똑같이
if b_cnt == 4:
remove(blue, i)
result += 1
# 0,1번 행에 1이 있으면 아래로 이동시켜야한다.
# 1이 0,1번행에 몇번 나왔는지 체크하기 위한 변수
green_count = 0
blue_count = 0
for i in range(2):
if 1 in green[i]:
green_count += 1
if 1 in blue[i]:
blue_count += 1
# 0,1번 행에 1이 존재한다면
if green_count:
# 존재 안할때까지
while green_count > 0:
# 바닥 인덱스를 지워야하므로 5로 지정
remove(green, 5)
green_count -= 1
# 파란색도 마찬가지
if blue_count:
while blue_count > 0:
remove(blue, 5)
blue_count -= 1
# 점수 출력
print(result)
# 초록, 파란에 남은 개수를 구하기 위한 count
count = 0
for i in range(6):
for j in range(4):
if blue[i][j] == 1:
count += 1
if green[i][j] == 1:
count += 1
print(count)✏️ Comment
녹색 부분과 파란부분 모두 밑으로 떨어진다고 생각하고 문제를 풀었다. 거기서 발생하는 index의 변화와 떨어지는 모양의 변화에 조심하였다.
떨어트리는 함수를 처음에는 green[i] = green[i+1] 이런 방식을 지정하였더니 얕은 복사가 되어서 id가 같아지게 되어서 오류가 났었다. 그것을 해결하기 위해 새롭게 2차원배열을 하나하나 확인하는 방식을 사용했다.
- 구현을 너무 어렵게 생각하지 말자 하나하나 따라가다보면 문제가 풀린다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ 1965🥈2] 상자넣기(Python) (1) | 2023.10.28 |
|---|---|
| [BOJ 23289 Platinum 5] 온풍기 안녕!(Python) (1) | 2023.10.12 |
| [BOJ 12015 🥇2] 가장 긴 증가하는 부분 수열 2 (Python) (0) | 2023.10.03 |
| [BOJ 2933 🥇1] 미네랄 (Python) (1) | 2023.10.01 |
| [BOJ 3019 🥈1] 테트리스 (Python) (0) | 2023.09.30 |
