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
# 21609 상어 중학교
def gravity():
global blocks
temp = 0
for c in range(N):
for r in range(N - 1, -1, -1):
# 아래 블록
cur_r = r
while cur_r > 0 and blocks[cur_r][c] == -2:
cur_r -= 1
if cur_r != r and blocks[cur_r][c] != -1:
temp = blocks[cur_r][c]
blocks[cur_r][c] = -2
blocks[r][c] = temp
return
def rotate():
global blocks
temp_blocks = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
temp_blocks[r][c] = blocks[c][N - 1 - r]
blocks = temp_blocks[:]
return
# 상 좌 하 우
dr = [-1, 0, 1, 0]
dc = [0, -1, 0, 1]
N, M = map(int, input().split())
blocks = [list(map(int, input().split())) for _ in range(N)]
score = 0
while True:
# 1. 가장 큰 블록 그룹 찾기
largest_block = list()
largest_rainbow = 0
visited = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):
if visited[r][c] == 1:
continue
cur_block = blocks[r][c]
if cur_block <= 0:
continue
visited[r][c] = 1
result_list = [[r, c]]
queue = [[r, c]]
rainbow_num = 0
while queue:
qr, qc = queue.pop(0)
for i in range(4):
cr = qr + dr[i]
cc = qc + dc[i]
if 0 <= cr < N and 0 <= cc < N and visited[cr][cc] == 0 and (
blocks[cr][cc] == 0 or blocks[cr][cc] == cur_block):
result_list.append([cr, cc])
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
rainbow_num += 1
visited[cr][cc] = 2
if len(largest_block) < len(result_list):
largest_block = result_list[:]
largest_rainbow = rainbow_num
elif len(largest_block) == len(result_list) and largest_rainbow <= rainbow_num:
largest_block = result_list[:]
largest_rainbow = rainbow_num
queue.append([cr, cc])
# 무지개 visited 초기화
for tr in range(N):
for tc in range(N):
if visited[tr][tc] == 2:
visited[tr][tc] = 0
# 1-1 block 갯수가 1 이하면 break
if len(largest_block) <= 1:
break
else:
score += len(largest_block) ** 2
# 2. 찾은 블록들 제거하기
for tr, tc in largest_block:
blocks[tr][tc] = -2
# 3. 중력
gravity()
# 4. 반시계 90도
rotate()
# 5. 중력
gravity()
print(score)
좋았던 점
예전에 봤던 문제였다. 그 땐 손도 대지 못했고, 지금은 풀어냈다.
친구가 카페에 있어서, 노트북을 들고 가서 코드를 작성했다. (2시간 가량) 실제 시험 환경에 대비한 점이 만족스럽다.
gravity, rotate를 구현할 때 함수를 따로 만들어서 구현해야겠다고 생각했고, 잘 구현해냈다.
처음 만든 코드에서 많은 부분을 고치지 않고 문제를 해결했다.
1시간 ~ 1시간 30분만에 코드 골격은 완성되었다. 좀 헤매서 2시간 30분 가량 소요되었다.
헤맨 부분
quque와 result_list를 따로 구현할 생각을 한 번에 하지 못했다. 주어진 예시에서, 최대 rainbow 갯수가 잘 구해지지 않아 20~30분 가량 헤맸다. result_list를 따로 만들어준 뒤, 문제를 해결할 수 있었다.
1, 3번 예시는 맞았는데 2번 예시에서 틀린 답이 출력되었다. 하나하나 그려보며, 코드를 따라가며 어디가 틀렸는지 디버깅해보았다. 디버깅 과정에서 큰 틀의 코드는 다 맞는데, 작은 부분에서 틀렸을 거란 확신이 있었다. gravity, rotate 함수는 잘 동작하는 것을 구현 직후 확인하였다.
문제 조건을 확인하던 중, 다음을 발견했다.
크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.무지개 블록의 수가 같을 때, 큰 행 / 큰 열을 찾아야 한다는 조건이었다.
다음 코드를 수정하여 문제를 해결하였다.
# 수정 전
elif len(largest_block) == len(result_list) and largest_rainbow < rainbow_num:
# 수정 후
elif len(largest_block) == len(result_list) and largest_rainbow <= rainbow_num:
무지개 블록의 수가 같을 때도 확인함으로써, r, c가 더 크면서 무지개 블록이 같을 때를 확인할 수 있었다.
위를 수정한 이후, 주어진 세 개의 입력에서 모두 정답 출력이 나왔고, 제출했다.
제출하자마자 틀렸다는 안내를 받았다.
카페에서의 공부를 정리하고 집에 오는 길에, r, c의 크기를 비교하는 로직이 틀렸을 것이란 예측을 하고 코드를 다시 봤다.
visited가 for문 안에 있어서, r, c를 탐색할 때마다 초기화되는 것을 발견하고, 이를 수정해주었다.
# 수정 전
for r in range(N):
for c in range(N):
...
visited = [[0] * N for _ in range(N)]
# 수정 후
visited = [[0] * N for _ in range(N)]
for r in range(N):
for c in range(N):이렇게 고쳤는데도, 제출하자마자 틀렸다는 안내를 받았다.
고민 결과, 자연수(일반 블럭)는 방문했을 경우 visited 처리를 해주면 되지만, 무지개 블럭(0)의 경우 다른 블록에서 다시 사용해볼 수 있음을 알게 되었다.
# 수정 전
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
rainbow_num += 1
# 수정 후
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
rainbow_num += 1
visited[cr][cc] = 0무지개 블록일 경우, visited를 0으로 만들어줬다.
그 결과, 제출시에 시간 초과가 발생하였다.
원하는거 다 들어줬는데 왜 안돼... 맞왜틀...
deque도 써보고, import sys
input = sys.stdin.readline을 써도 어림도 없었다.
이런저런 코드를 고쳐보던 중, pycharm 상에서 출력이 나오지 않는 것을 발견하였다. 왜 안나오지?
고민 끝에, 무지개블럭 옆에 무지개블럭이 있으면, visited = 0으로 되어서, 무지개블럭 사이를 왔다갔다하느라 while queue를 탈출하지 못한다는 결론을 내렸다.
그래서, 무지개 블럭은 visited = 1이 아닌 다른 숫자, visited = 2로 설정해놓은 뒤, queue를 탈출하고 나서 다음 r, c가 사용하기 전 무지개 블럭의 visited = 0으로 바꿔놔야겠다는 생각을 했다.
# 수정 전
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
rainbow_num += 1
visited[cr][cc] = 0
# 수정 후
visited[cr][cc] = 1
if blocks[cr][cc] == 0:
rainbow_num += 1
visited[cr][cc] = 2
# 수정 후 queue 밑에 새로 추가된 부분
# 무지개 visited 초기화
for tr in range(N):
for tc in range(N):
if visited[tr][tc] == 2:
visited[tr][tc] = 0이렇게 해서, 맞았다.
정답의 감동..
무지개 블럭이 문제라는 것을 인지하고 나서, 백준 질문 게시판을 슥 보았다. 왜 시간초과가 나는지 이해하지 못한 시점이었다. 질문 글의 제목을 통해 무지개 블럭이 포인트라는 것을 다시 인지하였다.
불행하게도 시간초과 관련 게시물은 없어서, 다시 혼자 연구하다가 풀게 되었다.
문제를 처음 마주했을 때, '이게 무슨 소리여? 내가 이걸 풀 수 있을까?' 라고 생각했는데, 잘 풀어내어 만족스럽다.
