[21609] python 상어 중학교

문제 링크

https://www.acmicpc.net/problem/21609

문제 요약

아이디어 정리

• 다음과 같은 순서대로 동작한다.
  1. 가장 넓은 범위를 가지는 블록을 선택해야 한다.
     1. bfs을 이용할 것이며, visited를 이용하여 방문한 경우를 제외하고 탐색한다.
        1. 여기서 rainbow에 해당하는 경우는 visited하지 않았다고 해서 다른 탐색을 할 때, 해당 영역도 포함하여 탐색이 가능하도록 해야 한다.
  2. 가장 넓은 범위를 가지는 블록의 값을 의미 없는 값인 -2로 설정한다.
  3. 중력과 회전하는 코드를 입력
  4. 위의 방법을 블록이 없을 때까지 반복한다.

문제 풀이

1. 아이디어 정리에 사용한 대로 코드 작성

from collections import deque
n, m = map(int, input().split())
block = [list(map(int, input().split())) for _ in range(n)]

dxy = [[0, 1], [0, -1], [1, 0], [-1, 0]]

def bfs(x, y, visited):
    q = deque()
    q.append([x, y])
    s = block[x][y]
    rainbow = []
    blocks = [[x, y]]
    block_cnt, rainbow_cnt = 1, 0 #같은 개수가 있을 경우 rainbow의 개수가 많은 순으로 접근할 것
    while q:
        x, y = q.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                if not visited[nx][ny]:
                    if block[nx][ny] == s:
                        visited[nx][ny] = True
                        q.append([nx, ny])
                        blocks.append([nx, ny])
                        block_cnt += 1

                    if block[nx][ny] == 0:
                        visited[nx][ny] = True
                        q.append([nx, ny])
                        rainbow.append([nx, ny])
                        blocks.append([nx, ny])
                        block_cnt += 1
                        rainbow_cnt += 1

    ## rainbow에 해당 할 경우 방문 기록 삭제
    for x, y in rainbow:
        visited[x][y] = False
    
    return block_cnt, rainbow_cnt, blocks, visited
            

def find_block():
    visited = [[False] * n for _ in range(n)]
    candidate = []
    for i in range(n):
        for j in range(n):
            if block[i][j] > 0 and not visited[i][j]:
                visited[i][j] = True
                block_cnt, rainbow_cnt, blocks, visited = bfs(i, j, visited)
                if block_cnt > 1:
                    candidate.append([block_cnt, rainbow_cnt, blocks])     # 후보에 block score, block 개수, block list

    if len(candidate) == 0:
        return None, 0
    
    candidate = sorted(candidate, reverse=True)

    blocks = candidate[0][2]
    added_score = candidate[0][0] ** 2

    for x, y in blocks:
        block[x][y] = -2
    
    return blocks, added_score

def gravity():
    for i in range(n - 2, -1, -1):
        for j in range(n):
            if block[i][j] > -1:
                r = i
                while True:
                    if 0 <= r + 1 < n and block[r + 1][j] == -2:
                        block[r + 1][j] = block[r][j]
                        block[r][j] = -2
                        r += 1
                    else:
                        break
                    
def rotate():
    global block
    new_block = []
    for j in range(n - 1, -1, -1):
        tmp = []
        for i in range(n):
            tmp.append(block[i][j])
        new_block.append(tmp)

    block = new_block

score = 0
while True:
    blocks, added_score = find_block()
    if blocks == None:
        break
    score += added_score

    gravity()
    rotate()
    gravity()
    
print(score)

• 대략적인 코드는 어느정도 완성 하였으나, 한끝차이로 답이 안나와서 시간을 많이 소요하였다.
• 문제 지문에서 블록의 개수, 무지개 블록의 개수, 등에 대한 전제조건이 있었는데 이와 관련된 코드를 자세히 읽지 않아서 오랜 시간을 소요하였다.