[BOJ] 21609. 상어 중학교(Python) / Simulation

21609번: 상어 중학교

2021 상반기 삼성 SW역량테스트 기출문제이다.

이번에 출제된 4문제 중 내 기준 가장 까다롭고 시간이 많이 든 문제였다.. BFS의 효율을 높이기 위한 전략이 필요했다.

완전 구현 문제로 고도의 집중력을 발휘해야 한다.

특별히 사용한 알고리즘은 가장 큰 그룹 찾을 때와 이를 지울 때의 BFS 정도이고, 완전 구현 문제이다.

• 사용 알고리즘 : Simultaion (+ BFS)
• 사용 자료구조 : Max Heap(최대 힙)
• 1번 조건 - "크기가 가장 큰 블록 그룹을 찾는다(BFS(), findMaxGroup() 함수). 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다." 을 만족시키기 위해 최대 힙을 사용했다.
  • 여기서, 나의 실수 포인트!(이것 때문에 디버깅으로 2시간 날렸다ㅠ 하)
  • 힙에 값이 담기지 않을 경우를 고려해줘야 한다.
    • 그러한 경우는 1. 가장 큰 블록 그룹 크기가 2보다 작음  2. 블록 그룹이 없음
• 2번 조건 - "1에서 찾은 블록 그룹의 모든 블록을 제거한다(BFS(), removeBlocks() 함수). 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B**2점을 획득한다."
  • removeBlocks(r, c)에 인자로 넣어줄 때, 최대 힙에서 값을 꺼내야 하므로 모두 -가 붙어있기 때문에
  • '-'를 꼭 붙여서 인자로 넘겨줘야 한다 removeBlocks(-row, -col)
• 3, 5번 조건 - 중력 구현(gravity() 함수)
• 4번 조건 - 반시계방향으로 90도 회전 구현(turnLeft90() 함수)
• 이처럼 약간의 BFS와 문제 주어진 조건대로 그대로 구현만 하면 된다.
• 자세한 설명은 아래 주석 처리 해두었다.

 

파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque
from heapq import heappush, heappop

dr = (-1, 1, 0, 0)
dc = (0, 0, -1, 1)

# 시작 위치, 시작번호, 그릴 번호
def bfs(sr, sc, num):
    temp = A[sr][sc]
    Q = deque([(sr, sc)])
    visited[sr][sc] = num
    blockCnt, rainbowCnt = 1, 0
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N): continue # 격자 밖
            # 이미 방문했거나 검은색 블록 / 빈 공간이면
            if visited[nr][nc] == num or A[nr][nc] <= -1:
                continue
            # 같은 숫자이거나 무지개 블록이면
            if A[nr][nc] == temp or A[nr][nc] == 0:
                visited[nr][nc] = num   # 방문 표시
                Q.append((nr, nc))      # 큐에 담기
                blockCnt += 1           # 블록 갯수 += 1
                if A[nr][nc] == 0:
                    rainbowCnt += 1     # 무지개 블록 갯수
    # (가장 큰 블록 그룹 > 무지개 블록 수 많은 것 > 행이 가장 큰 것 > 열이 가장 큰 것)
    heappush(pq, (-blockCnt, -rainbowCnt, -sr, -sc))
    return

def removeBlocks(sr, sc):
    start = A[sr][sc]
    A[sr][sc] = -2          # 첫 위치 맵에 -2로 표시(빈 공간)
    visited[sr][sc] = -1    # 첫 위치 -1로 방문 표시(visited 재사용)
    Q = deque([(sr, sc)])
    while Q:
        r, c = Q.popleft()
        for d in range(4):
            nr = r + dr[d]
            nc = c + dc[d]
            if not (0 <= nr < N and 0 <= nc < N): continue     # 격자 밖
            # 빈 공간/검은 블록이거나 이미 방문한 곳이면               
            if A[nr][nc] <= -1 or visited[nr][nc] == -1: continue
            # 같은 숫자 블록이거나 무지개 블록이면
            if A[nr][nc] == start or A[nr][nc] == 0:
                A[nr][nc] = -2          # 지운 곳 표시
                visited[nr][nc] = -1    # 방문 표시
                Q.append((nr, nc))      # 재탐색을 위해 큐에 담기

def findMaxBlockGroup():
    global score, blockGroup
    num = 1
    for r in range(N):
        for c in range(N):
            # 검은 블록/빈 공간이거나 무지개 블록이거나 이미 방문했으면
            if A[r][c] <= -1 or A[r][c] == 0 or visited[r][c]:
                continue
            if 1 <= A[r][c] <= M:
                bfs(r, c, num)
                num += 1

    if pq:      # 우선순위 큐에 값이 있는 경우에만
        blockCnt, rainbowCnt, row, col = heappop(pq)    # 최대 힙
        if -blockCnt >= 2:   # 그룹에 속한 블록의 개수는 2보다 크거나 같아야 함
            score += blockCnt ** 2	# 점수 더하기
            removeBlocks(-row, -col)
        else:
            blockGroup = False      # 가장 블록 그룹이 2보다 작음 => 불가능
    else:
        blockGroup = False          # 블록 그룹 없음 => 불가능

def gravity():
    for c in range(N):
        blocks = deque()
        sr, sc = N-1, c
        for r in range(N-1, -1, -1):
            if A[r][c] >= 0:    # 블록 or 일반 블록이면
                blocks.append(A[r][c])      # 블록 큐에 추가
                A[r][c] = -2    # 빈 공간으로 만들기
            if A[r][c] == -1:
                while blocks:   # 큐에 값이 있는 동안 pop하며 해당 열에 값 채우기
                    A[sr][sc] = blocks.popleft()
                    sr -= 1
                blocks = deque()    # 큐 비우기
                sr = r-1
        if blocks:          # 마지막 부분 마저 값 채우기
            while blocks:
                A[sr][sc] = blocks.popleft()
                sr -= 1

def turnLeft90():
    newA = []
    for c in range(N-1, -1, -1):
        col = []
        for r in range(N):
            col.append(A[r][c])
        newA.append(col)
    return newA

# main
N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

score = 0
blockGroup = True    # 블록 그룹 존재 여부
while True:
    visited = [[0] * N for _ in range(N)]
    pq = []
    findMaxBlockGroup()    # 가장 큰 블록그룹 찾기 
    if not blockGroup:     # 종료 조건
        break
    gravity()           # 중력
    A = turnLeft90()    # 반시계방향으로 90도 회전
    gravity()           # 중력
print(score)

---

• 시간 : 264ms / 메모리 :128216 kb(PyPy3 제출)
• 고찰 : 구현력. 오직 구현력을 보는 문제이다. 약간의 효율성까지 고려해 짜다보니 시간이 좀 많이 걸렸다. 고도의 집중력을 발휘해 코드 한줄 한줄 끝까지 쫓아가면서 디버깅에 성공했다. 정말 오래 걸린 문제였다ㅠ 3시간+a(디버깅까지,,) 혼자 힘으로 풀어내 그나마 다행이었지만, 시간이 많이 들어 아쉬웠다. 더 더 빠르고 정확하게 푸는 연습을 해야겠다. 파이팅!