문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 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이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다.
접근
문제에서 주어진 조건대로 구현을 하면 되었다. 블록그룹을 찾을 때는 BFS를 사용하였다.
해당 문제를 풀면서 구현해야할 기능 별로 함수를 만들어서 사용하는 것이 디버깅할 때도 도움이 많이 되었을 것 같다.
또한 위의 문제처럼 특정조건 전에는 계속해서 순환될 때 첫 번째 싸이클에서 결과값을 모두 확인하도록 한다.
이후에 디버깅을 쉽게하기 위함이다.
구현
- 블록그룹에서 블록의 개수가 2이상이고 일반블록이 적어도 하나 이상 포함되지 않았다면 반복문을 종료한다.
- bfs를 통해 블록그룹을 찾는다.
- 이후 블록그룹에 해당되는 위치의 블록을 제거하고 제거한 개수를 카운트한다.
- 블록을 제거한 개수 ** 2만큼 최종해를 증가시킨다.
- 이제 중력을 적용한 후에 90도 반 시계 방향으로 회전한다.
- 다시 중력을 적용한다.
while True:
block_group = [[0 for _ in range(N)] for _ in range(N)]
main_value = [-1, -1, -1] # 블록개수, 무지개블록 개수, 기준블록 좌표
for y in range(N):
for x in range(N):
if board[y][x] > 0:
new_block_group, b, r, p = bfs(y, x, board[y][x])
if b == -1:
continue
update_value(new_block_group, b, r, p)
if main_value[0] == -1:
break
count = 0
for y in range(N):
for x in range(N):
if block_group[y][x]:
board[y][x] = -2
count += 1
answer += (count ** 2)
for x in range(N):
for y in range(N-1, -1, -1):
if board[y][x] >= 0:
number = board[y][x]
board[y][x] = -2
ny = y
nx = x
while True:
ny += 1
nx += 0
if (not check_range(ny, nx)) or board[ny][nx] == -1:
ny -= 1
break
if board[ny][nx] >= 0:
ny -= 1
break
board[ny][nx] = number
new_board = [[ 0 for _ in range(N)] for _ in range(N)]
pos = 0
for x in range(N-1, -1, -1):
for y in range(N):
ny = pos // N
nx = pos % N
new_board[ny][nx] = board[y][x]
pos += 1
board = new_board
for x in range(N):
for y in range(N-1, -1, -1):
if board[y][x] >= 0:
number = board[y][x]
board[y][x] = -2
ny = y
nx = x
while True:
ny += 1
nx += 0
if (not check_range(ny, nx)) or board[ny][nx] == -1:
ny -= 1
break
if board[ny][nx] >= 0:
ny -= 1
break
board[ny][nx] = number
print(answer)전체 코드
이후에 리팩토링 과정을 거쳐야겠다.
import sys
from _collections import deque
input = sys.stdin.readline
def check_range(y, x):
return (0 <= y < N) and (0 <= x < N)
def update_value(new_block_group, b, r, p):
global main_value, block_group
if main_value[0] < b:
main_value[0] = b
main_value[1] = r
main_value[2] = p
block_group = new_block_group
elif main_value[0] == b:
if main_value[1] < r:
main_value[0] = b
main_value[1] = r
main_value[2] = p
block_group = new_block_group
elif main_value[1] == r:
if main_value[2] < p:
main_value[0] = b
main_value[1] = r
main_value[2] = p
block_group = new_block_group
def bfs(y, x, number):
q = deque()
visited = [[0 for _ in range(N)] for _ in range(N)]
q.append((y, x))
visited[y][x] = 1
block_count = 0
rainbow_count = 0
block_pos = 10000
dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]
while q:
cy, cx = q.popleft()
block_count += 1
if board[cy][cx] == 0:
rainbow_count += 1
if block_pos > cy * 100 + cx and board[cy][cx] == number:
block_pos = cy * 100 + cx
for d in range(4):
ny = cy + dy[d]
nx = cx + dx[d]
if check_range(ny, nx) and board[ny][nx] != -1 and visited[ny][nx] == 0:
if board[ny][nx] == -2:
continue
if board[ny][nx] == number or board[ny][nx] == 0:
q.append((ny, nx))
visited[ny][nx] = 1
if block_count < 2:
return visited, -1, -1, -1
return visited, block_count, rainbow_count, block_pos
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
answer = 0
while True:
block_group = [[0 for _ in range(N)] for _ in range(N)]
main_value = [-1, -1, -1] # 블록개수, 무지개블록 개수, 기준블록 좌표
for y in range(N):
for x in range(N):
if board[y][x] > 0:
new_block_group, b, r, p = bfs(y, x, board[y][x])
if b == -1:
continue
update_value(new_block_group, b, r, p)
if main_value[0] == -1:
break
count = 0
for y in range(N):
for x in range(N):
if block_group[y][x]:
board[y][x] = -2
count += 1
answer += (count ** 2)
for x in range(N):
for y in range(N-1, -1, -1):
if board[y][x] >= 0:
number = board[y][x]
board[y][x] = -2
ny = y
nx = x
while True:
ny += 1
nx += 0
if (not check_range(ny, nx)) or board[ny][nx] == -1:
ny -= 1
break
if board[ny][nx] >= 0:
ny -= 1
break
board[ny][nx] = number
new_board = [[ 0 for _ in range(N)] for _ in range(N)]
pos = 0
for x in range(N-1, -1, -1):
for y in range(N):
ny = pos // N
nx = pos % N
new_board[ny][nx] = board[y][x]
pos += 1
board = new_board
for x in range(N):
for y in range(N-1, -1, -1):
if board[y][x] >= 0:
number = board[y][x]
board[y][x] = -2
ny = y
nx = x
while True:
ny += 1
nx += 0
if (not check_range(ny, nx)) or board[ny][nx] == -1:
ny -= 1
break
if board[ny][nx] >= 0:
ny -= 1
break
board[ny][nx] = number
print(answer)'알고리즘 풀이 > 백준' 카테고리의 다른 글
| [백준 21611] 마법사 상어와 블리자드 (0) | 2021.07.13 |
|---|---|
| [백준 10423] 전기가 부족해 (0) | 2021.07.12 |
| [백준 21610] 마법사 상어와 비바라기 (0) | 2021.07.10 |
| [백준 20056] 마법사 상어와 파이어볼 (0) | 2021.07.09 |
| [백준 14465] 소가 길을 건너간 이유5 (0) | 2021.07.08 |