21609 - 상어 중학교

 

---

 

문제

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

21609번: 상어 중학교

 

풀이

 

요구사항과 조건이 굉장히 많은 구현 문제다.

 

풀이를 하다보면 놓치는 부분이 많을것이라고 생각하여서 우선 요구사항을 내가 이해하기 편하도록 작성했고, 그에 따른 슈도코드나 솔루션도 생각나는대로 작성했다.

 

대충 이런느낌으로 코드 작성하기전에 쭈욱 작성하고 시작했다.

 

해당 문제의 큰 흐름을 확인해보자.

 

1. 존재하는 블록그룹을 확인한다.
   • 우선 탐색은 bfs로 가정한다.
   • 블록그룹은 우선 무지개블록, 검은블록이 아닌 일반블록이 하나는 있어야한다. 
   • 또한 기준 블록의 정보를 알아야하는데, 조건을 보면 좌상단에 가장 가까운 블록임을 알 수 있다.
   • 따라서 좌상단부터 우하단까지 블록 배열을 순회하면서 일반블록이면 bfs를 수행해주면 된다.
   • 그 안에서는 같은 블록이거나 무지개 블록이면 탐색을 계속하도록 만들고, 무지개 블록이면 무지개 블록 개수를 늘려준다. 블록그룹사이즈는 항상 늘려주면 된다.
   • 또한 해당 블록그룹이 삭제 그룹으로 선택되었을 경우를 대비하여 삭제할 좌표들도 저장해준다. 
   • 과정이 끝나고 블록그룹이 2이상이면 True와 함께 정보들을 반환해준다. 
2. 블록그룹을 갱신해준다.
   • 1번에서 반환한 블록그룹과, 기존에 선별된 블록그룹을 비교한다.
   • 이 부분은 조건에 따라서 수행하면 된다.
   • 크기순으로 비교, 무지개 블록순으로 비교, 이후에는 행과 열을 각각 비교해주면 된다.
3. 블록 그룹 삭제
   • 1번에서 저장해둔 삭제 배열을 순회하면서 블록그룹에서 값을 삭제하면 된다.
   • 이 값은 사용자 임의로 지정해두면 되고 나는 -9로 설정했다.
   • 그룹개수 * 2 만큼 정답에 더해주면 된다.
4. 중력처리
   • 왼쪽부터 오른쪽으로 열 하나씩 처리하였으며, 밑에서부터 검사했다.
   • 해당칸이 빈칸이라면 내 위쪽의 값들을 확인해본다.
   • 처음으로 찾은값이 -1이라면 못당겨오므로 패스하고, 그게 아니라면 현재칸에 그 값을 대입해준다.
   • 그리고 원래 값이 있던곳은 빈칸으로 처리하는것을 잊지말자.
   • 3중 for문으로 구현할 수 있다.
5. 회전
   • 회전은 그냥 회전하면 된다.. zip을 활용한 회전 테크닉을 사용하였다.

 

위의 과정을 반복하다가, 조건에 해당하는 블록그룹이 하나도 없으면 break하고 답을 출력하면 된다.

 

 

코드

import copy
from sys import stdin
from collections import deque

# 해당 그룹의 정보들을 탐색 및 반환한다.
# 성공여부, 블록그룹의 사이즈, 무지개 블록의 개수, 삭제해야할 좌표를 담은 배열
def getGroupsInfo(x, y):
    global normalVisited, dx, dy, normalVisited
    blockNum = board[x][y]
    groupSize = 1
    rainbowNum = 0
    visited = [ [False for _ in range(n)] for _ in range(n) ]
    deletePostions = [(x, y)]
    q = deque()
    q.append((x, y))
    visited[x][y] = True

    while q :
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<n and 0<=ny<n and not visited[nx][ny]:
                if board[nx][ny] == 0 or board[nx][ny] == blockNum:

                    if board[nx][ny] == 0 :
                        rainbowNum += 1
                    else:
                        normalVisited[nx][ny] = True

                    groupSize += 1
                    q.append((nx, ny))
                    visited[nx][ny] = True
                    deletePostions.append((nx, ny))
    if groupSize < 2:
        return False, groupSize, rainbowNum, deletePostions
    return True, groupSize, rainbowNum, deletePostions

def update(t_groupSize, t_rainbowNum, t_position, t_deletePositions):
    global  position, groupSize, rainbowNum, deletePositions
    position = t_position
    groupSize = t_groupSize
    rainbowNum = t_rainbowNum
    deletePositions = copy.deepcopy(t_deletePositions)


# 조건에 따라 갱신해준다.
def updateValues(t_groupSize, t_rainbowNum, t_position, t_deletePositions):
    global position, groupSize, rainbowNum, deletePositions

    if t_groupSize > groupSize:
        update(t_groupSize, t_rainbowNum, t_position, t_deletePositions)

    elif t_groupSize == groupSize:
        if t_rainbowNum > rainbowNum:
            update(t_groupSize, t_rainbowNum, t_position, t_deletePositions)

        elif t_rainbowNum == rainbowNum:
            if t_position[0] > position[0]:
                update(t_groupSize, t_rainbowNum, t_position, t_deletePositions)

            elif t_position[0] == position[0]:
                if t_position[1] > position[1]:
                    update(t_groupSize, t_rainbowNum, t_position, t_deletePositions)

def deleteBlocks():
    global deletePositions
    for val in deletePositions:
        board[val[0]][val[1]] = -9


# 특정칸이 빈칸이라면 -> 내 위 칸들을 모두 검사하면서 -1이 아니라면 내 위치에 두게 한다.
# 찾은값은 -9로 변경시켜줘야한다.
def gravity():
    global board

    for i in range(n):
        for j in range(n-1, 0, -1):

            # 해당칸이 빈칸이라면 위에 있는 친구를 땡겨준다.
            if board[j][i] == -9:
                # 윗칸을 순회한다.
                for k in range(j-1, -1, -1):
                    # 검은색블록이면 못 당겨온다.
                    if board[k][i] == -1:
                        break
                    # 빈칸이 아닌 다른값이라면 당겨준다.
                    if board[k][i] != -9 :
                        board[j][i] = board[k][i]
                        board[k][i] = -9
                        break

def rotate():
    global board
    board = list(map(list, zip(*board)))[::-1]

# Initialize
n, m = map(int, input().split())
board = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n) ]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
answer = 0
while True:
	# normalVisited => 같은 블록그룹은 한번만 방문하도록 하기위함
    normalVisited = [[False for _ in range(n)] for _ in range(n)]
    isExist = False
    position = (0, 0)
    groupSize = 0
    rainbowNum = 0
    deletePositions = []
    for i in range(n):
        for j in range(n):
            # 무지개블록이나, 검은색 블록이 아니고, 빈칸이 아니고, 방문하지 않았다면
            if board[i][j] != -1 and board[i][j] != 0 and board[i][j] != -9 and not normalVisited[i][j]:
                normalVisited[i][j] = True
                t_position = (i, j)
                t_possible, t_groupSize, t_rainbowNum, t_deletePositions = getGroupsInfo(i, j)
                if not t_possible:
                    continue
                # 만족하는 그룹이 한개라도 있다면 True, 그리고 조건에 따른 갱신
                isExist = True
                updateValues(t_groupSize, t_rainbowNum, t_position, t_deletePositions)
    if not isExist:
        break
    answer += groupSize ** 2

    # 해당 칸 삭제 -> 중력 작용 -> 반시계 회전 -> 중력 작용
    deleteBlocks()
    gravity()
    rotate()
    gravity()

print(answer)

 

후기

 

코드는 길었지만 시간은 생각보다 오래 걸리지 않았다. 요구사항을 깔끔하게 잘 정리한 덕분이라고 생각한다.