https://www.acmicpc.net/problem/21609
[21609번: 상어 중학교
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록
www.acmicpc.net](https://www.acmicpc.net/problem/21609)
문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 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, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다.
제한
- 1 ≤ N ≤ 20
- 1 ≤ M ≤ 5
풀이
처음 풀어본 상어 어쩌구 문제..
크게 풀어야 할 문제들을 함수로 나누어 퀘스트 깨듯이 풀면 체계적으로 풀 수 있다.
1. 블록 그룹 찾기
2. 블록 제거
3. 중력
4. 회전
1. 블록 그룹 찾기
- bfs 알고리즘을 사용
- 블록 수가 가장 많은 블록 그룹을 선택 해야 하기 때문에 완전탐색으로 모두 확인
- 찾은 블록 그룹들 중 우선순위가 가장 높은 것을 선택 -> sort를 통해 우선순위 조건을 만족 시킨다
def is_board(x ,y):
if 0 <= x < N and 0 <= y < N:
return True
return False
def bfs(x, y, color):
q = deque()
q.append([x, y])
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
block_cnt, rainbow_cnt = 1, 0 # 블록 개수, 무지개 블록 개수(우선순위)
blocks, rainbows = [[x, y]], [] # 블록 좌표 리스트, 무지개 리스트
while q:
x, y = q.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if not is_board(nx, ny):
continue
if visited[nx][ny]:
continue
# 격자 내 존재, 방문 안한 일반 블록
if arr[nx][ny] == color:
visited[nx][ny] = 1
q.append([nx, ny])
block_cnt += 1
blocks.append([nx, ny])
# 격자 내 존재, 방문 안한 무지개 블록
elif arr[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny])
block_cnt += 1
rainbow_cnt += 1
rainbows.append([nx, ny])
# 무지개 블록 중복 가능 하기 때문에 방문 기록 삭제
for x, y in rainbows:
visited[x][y] = 0
return [block_cnt, rainbow_cnt, blocks + rainbows]2. 블록 제거
- 블록 그룹에 존재하는 격자 값을 -2로 조정하여 빈칸으로 만들어 줌
def remove(block):
# 제거 블록을 -2로 지정
for x, y in block:
arr[x][y] = -23. 중력
- 중력은 밑으로 내리는 역할을 하므로 밑에서 부터 확인하는게 편리
- 마지막 줄은 어짜피 확인할 필요가 없으므로 N-1행부터 확인
- 내려갈 칸이 격자 내부인지, 빈칸인지 확인(모든 숫자를 내릴 때 까지 반복)
# 마지막 윗 칸부터 한 칸씩 확인
for i in range(N - 2, -1, -1):
for j in range(N):
# 검정 블록(-1), 빈칸(-2) 무지개,일반 블록(>=0)
if arr[i][j] > -1:
pointer = i
# 경계 지점에 오거나 다른 블록 앞에 닿을 때까지 반복
while 0 <= pointer + 1 < N and arr[pointer + 1][j] == -2:
arr[pointer + 1][j] = arr[pointer][j]
arr[pointer][j] = -2
pointer += 1
4. 회전
- 90도 반시계 방향으로 회전해야함
- 공식처럼 시계, 반시계 방향으로 회전하는 관계식을 외워두면 시간을 단축 할 수 있다
- 물론 처음 한번은 왜 이렇게 회전하는지 생각해 두면 더 이해가 잘 되겠지?!
| 시계방향 90도 회전 | new_arr[ n - 1 - j ][ i ] = arr[ i ][ j ] |
| 반시계 방향 90도 회전 | new_arr[ j ][ n - 1 - i ] = arr[ i ][ j ] |
코드
from collections import deque
def is_board(x ,y):
if 0 <= x < N and 0 <= y < N:
return True
return False
def bfs(x, y, color):
q = deque()
q.append([x, y])
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
block_cnt, rainbow_cnt = 1, 0 # 블록 개수, 무지개 블록 개수(우선순위)
blocks, rainbows = [[x, y]], [] # 블록 좌표 리스트, 무지개 리스트
while q:
x, y = q.popleft()
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if not is_board(nx, ny):
continue
if visited[nx][ny]:
continue
# 격자 내 존재, 방문 안한 일반 블록
if arr[nx][ny] == color:
visited[nx][ny] = 1
q.append([nx, ny])
block_cnt += 1
blocks.append([nx, ny])
# 격자 내 존재, 방문 안한 무지개 블록
elif arr[nx][ny] == 0:
visited[nx][ny] = 1
q.append([nx, ny])
block_cnt += 1
rainbow_cnt += 1
rainbows.append([nx, ny])
# 무지개 블록 중복 가능 하기 때문에 방문 기록 삭제
for x, y in rainbows:
visited[x][y] = 0
return [block_cnt, rainbow_cnt, blocks + rainbows]
def remove(block):
# 제거 블록을 -2로 지정
for x, y in block:
arr[x][y] = -2
def gravity(arr):
# 마지막 윗 칸부터 한 칸씩 확인
for i in range(N - 2, -1, -1):
for j in range(N):
# 검정 블록(-1), 빈칸(-2) 무지개,일반 블록(>=0)
if arr[i][j] > -1:
pointer = i
# 경계 지점에 오거나 다른 블록 앞에 닿을 때까지 반복
while 0 <= pointer + 1 < N and arr[pointer + 1][j] == -2:
arr[pointer + 1][j] = arr[pointer][j]
arr[pointer][j] = -2
pointer += 1
def rotate(arr):
temp = [[0] * N for _ in range(N)]
for i in range(N):
for j in range(N):
# 단순 계산 식 (반시계 방향 좌표 관계 참조)
temp[N - 1 - j][i] = arr[i][j]
return temp
N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
score = 0
# 오토 플레이
while True:
visited = [[0] * N for _ in range(N)]
blocks = []
# 1. 블록 그룹 찾기(완전 탐색)
for i in range(N):
for j in range(N):
# 일반 블럭 이고 방문 하지 않은 블럭
if arr[i][j] > 0 and not visited[i][j]:
visited[i][j] = 1
block_group = bfs(i, j, arr[i][j])
# 블럭 그룹의 크기 >= 2
if block_group[0] >= 2:
blocks.append(block_group)
# [블록 개수, 무지개 개수, 좌표(행,열)]로 구성된 리스트를 정렬
# 우선순위 항목 만족
blocks.sort(reverse=True)
# 블록 그룹이 없는 경우 stop
if not blocks:
break
# 2. 블록 제거
remove(blocks[0][2])
score += blocks[0][0] ** 2
# 3. 중력
gravity(arr)
# 4. 회전
arr = rotate(arr)
# 5. 중력
gravity(arr)
print(score)'프로그래밍 > Python' 카테고리의 다른 글
| [백준] 17142번 / 연구소 3 / 파이썬(Python) (0) | 2023.10.26 |
|---|---|
| [백준] 15686번 / 치킨 배달 / 파이썬(Python) (0) | 2023.10.26 |
| [백준] 14503번 / 로봇청소기 / Python(파이썬) (0) | 2023.10.25 |
| [백준] 14499번 / 주사위 굴리기 / Python(파이썬) (0) | 2023.10.25 |
| [프로그래머스] 디스크 컨트롤러 / 힙(heap) / python (0) | 2023.06.27 |
댓글