JB의 이모저모
[BOJ 21609 🥇2] 상어 중학교 (Python) 본문
https://www.acmicpc.net/problem/21609
21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net
문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 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 = 5, M = 3인 경우의 예시이다.
| 2 | 2 | -1 | 3 | 1 |
| 3 | 3 | 2 | 0 | -1 |
| 0 | 0 | 0 | 1 | 2 |
| -1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 2 | 2 | 1 |
여기서 찾을 수 있는 크기가 가장 큰 블록 그룹을 다음과 같이 빨간색으로 표시했다.
| 2 | 2 | -1 | 3 | 1 |
| 3 | 3 | 2 | 0 | -1 |
| 0 | 0 | 0 | 1 | 2 |
| -1 | 3 | 1 | 3 | 2 |
| 0 | 3 | 2 | 2 | 1 |
블록 그룹이 제거되면 다음과 같이 변하고, 점수 82점을 획득한다.
| 2 | 2 | -1 | 3 | 1 |
| 2 | 0 | -1 | ||
| 1 | 2 | |||
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 1 |
중력이 작용하면 다음과 같이 변한다.
| -1 | 3 | 1 | ||
| 0 | -1 | |||
| 2 | 2 | 1 | 2 | |
| -1 | 1 | 3 | 2 | |
| 2 | 2 | 2 | 1 |
90도 반시계방향으로 회전한 결과는 다음과 같다.
| 1 | -1 | 2 | 2 | 1 |
| 3 | 0 | 1 | 3 | 2 |
| -1 | 2 | 1 | 2 | |
| 2 | ||||
| 2 | -1 |
다시 여기서 중력이 작용하면 다음과 같이 변한다.
| 1 | -1 | |||
| 3 | 2 | 2 | 1 | |
| -1 | 1 | 3 | 2 | |
| 2 | 1 | 2 | ||
| 0 | 2 | -1 | 2 |
오토 플레이가 모두 끝났을 때 획득한 점수의 합을 구해보자.
입력
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다.
제한
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 5
예제 입력 1
5 3
2 2 -1 3 1
3 3 2 0 -1
0 0 0 1 2
-1 3 1 3 2
0 3 2 2 1
예제 출력 1
77
예제 입력 2
6 4
2 3 1 0 -1 2
2 -1 4 1 3 3
3 0 4 2 2 1
-1 4 -1 2 3 4
3 -1 4 2 0 3
1 2 2 2 2 1
예제 출력 2
125
예제 입력 3
4 3
1 1 1 3
3 2 3 3
1 2 -1 3
-1 -1 1 1
예제 출력 3
33
⭕ CODE
from collections import deque
from copy import deepcopy
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
# 회전 함수
def rotate():
global arr
new = [[0] * n for _ in range(n)]
# 90도 반시계방향 회전
# 1행 -> 1열, 2행 -> 2열,,,,
# 00 04, 01 14, 02 24, 03 34, 04 44
# 10 03, 11 13, 12 23, 13 33,
for i in range(n):
for j in range(n):
new[i][j] = arr[j][n - 1 - i]
arr = deepcopy(new)
return arr
# 중력
def drop():
# 떨어트릴 높이 구하기
for i in range(n - 2, -1, -1):
for j in range(n - 1, -1, -1):
cnt = 0
# 0이상인 애들은 떨어트려야한다.
if arr[i][j] >= 0:
# 다른 블록에 닿이거나 격자 경계 만나기 전까지 높이 늘려주기
while True:
cnt += 1
if i + cnt >= n:
break
if arr[i + cnt][j] >= -1:
break
# 2이상 떨어지는 애들 떨어트려주기
if cnt > 1:
arr[i + cnt - 1][j] = arr[i][j]
# 원래 자리는 빈칸인 -2로
arr[i][j] = -2
return arr
# 가장 큰 그룹을 찾고 제거하는 함수
def find():
global score
visited = [[0] * n for _ in range(n)]
# 일반 블록 수
color = 0
# 무지개 블록 수
rainbow = 0
# 가장 큰 무리 big
big = []
# 기준블록의 x,y
standard_x = 0
standard_y = 0
for i in range(n):
for j in range(n):
# 일반 블록이고 방문한적이 없다면
if arr[i][j] > 0 and visited[i][j] == 0:
q = deque()
q.append((i, j))
visited[i][j] = 1
# 현재 탐색하는 것의 일반블록 수
now_color = 0
# 현재 탐색하는 것의 무지개블록 수
now_rainbow = 0
now_color += 1
# 현재 색
now = arr[i][j]
# 현재 탐색하는 그룹
group = []
group.append((i, j))
# 기준 블록을 찾기 위한 리스트
standard = []
standard.append((i, j))
while q:
x, y = q.popleft()
for a in range(4):
nx = x + dx[a]
ny = y + dy[a]
if 0 <= nx < n and 0 <= ny < n:
# 다음 위치가 현재 색상과 같고 방문한 적이 없으면
if arr[nx][ny] == now and visited[nx][ny] == 0:
q.append((nx, ny))
visited[nx][ny] = 1
# 일반 블록 색 개수 + 1
now_color += 1
# 그룹에 추가
group.append((nx, ny))
# 기준에 추가
standard.append((nx, ny))
# 다음 위치가 무지개 블록이고 현재 그룹에 없다면(방문한적이 없다면)
elif arr[nx][ny] == 0 and (nx, ny) not in group:
q.append((nx, ny))
# 현재 무지개 블록 개수 + 1
now_rainbow += 1
# 그룹에 추가
group.append((nx, ny))
# 기준 블록의 경우 무지개 블록이 아니고
# 행의 번호가 가장 작고 열의 번호가 가장 작아야하므로
# 그냥 sort()를 해준다.
standard.sort()
# 현재 기준 x,y 지정
now_standard_x = standard[0][0]
now_standard_y = standard[0][1]
# 현재 일반 블록과 무지개 블록이 이전의 개수보다 크다면
if now_color + now_rainbow > color + rainbow:
# 일반 블록 수와 무지개 블록의 수를 갱신해주고
color = now_color
rainbow = now_rainbow
# 가장 큰 무리도 바꿔준다.
big = group
# 기준 x,y도 갱신
standard_x = now_standard_x
standard_y = now_standard_y
# 일반 블록과 무지개 블록의 수가 이전과 같다면
if now_color + now_rainbow == color + rainbow:
# 다음 기준인 무지개 블록의 수로 판별 후 갱신
if now_rainbow > rainbow:
color = now_color
rainbow = now_rainbow
big = group
standard_x = now_standard_x
standard_y = now_standard_y
# 만약 무지개 블록의 수도 같다면
elif now_color == color:
# 그 다음 기준인 기준 행(x)가 큰것으로
if now_standard_x > standard_x:
big = group
standard_x = now_standard_x
standard_y = now_standard_y
# 기준 행(x)가 같다면 기준 열(y)가 큰것으로 갱신
if now_standard_x == standard_x and now_standard_y > standard_y:
big = group
standard_x = now_standard_x
standard_y = now_standard_y
# 가장 큰 그룹에 속한 블록의 개수(일반 블록 + 무지개 블록) 가 2개 이상이면
if color + rainbow >= 2:
# 점수에 추가
score += (color + rainbow) ** 2
# 가장 큰 그룹의 모든 블록 제거
for x, y in big:
arr[x][y] = -2
flag = 0
else:
flag = 1
return flag
# n*n 격자 m개 색상의 일반 블록
n, m = map(int, input().split())
# 검은색 블록 -1
# 무지개 블록 0
# 일반 블록 m 이하의 자연수
arr = [list(map(int, input().split())) for _ in range(n)]
# 점수 score
score = 0
while True:
# 만약 제거할것이 없다면 종료
if find() == 1:
break
# 제거 후 1차 중력
drop()
# 90도 반시계 방향 회전
rotate()
# 회전 후 2차 중력
drop()
# 점수 출력
print(score)✏️ Comment
기준 블록의 조건은 가장 작은 행과 열이였지만
가장 큰 블록 그룹의 조건은 기준 블록중 가장 큰 행과 열이였다.
이 부분에서 기준 블록 또한 가장 큰 행과 열로 구하여 틀렸었다.
bfs를 사용한 구현문제라고 생각한다. 회전과 중력은 자주 나오니 더 시간이 짧은 코드가 있는지 공부해야겠다.
- 항상 느끼지만 문제에서 주는 조건을 명확하게 해야한다. 항상 조건을 꼼꼼하게 체크하자
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ 5213🥇2] 과외맨 (Python) (0) | 2023.12.29 |
|---|---|
| [BOJ 16985🥇2] Maaaaaaaaaze (Python) (1) | 2023.12.15 |
| [BOJ 16973 🥇4] 직사각형 탈출 (Python) (1) | 2023.11.28 |
| [BOJ 12026 🥈1] BOJ 거리 (Python) (1) | 2023.11.20 |
| [BOJ 3190 🥇4] 뱀 (Python) (0) | 2023.11.11 |
