BOJ - 상어 중학교 21609번 (python)

❓ 문제 - 백준 상어 중학교 21609번 - python 풀이법

 

출처 

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

21609번: 상어 중학교

 

 

📝 문제해결법

1. 이 문제는 구현+BFS으로 풀었다.

• board에 격자판에 대한 정보를 담고, while문을 통해 오토 플레이를 반복한다.
• visited 함수로 BFS를 돌릴 때 방문처리와 동시에 블록 그룹의 번호를 저장한다. 무지개 블록의 경우 어떤 일반 블록에도 같이 껴서 블록 그룹을 형성할 수 있으므로 visited 값을 기본 값이 0이 아닌 배열 형태로 바꾼다.
• 격자의 모든 행과 열을 돌면서 일반 블록이면서 아직 방문하지 않은 곳은 BFS를 돌려서 블록 그룹의 사이즈와, 블록 그룹 안에 있는 무지개 블록의 갯수를 리턴 받는다. 만약 블록 그룹의 사이즈가 1이라면 그룹을 형성할 수 없고, 그룹을 형성했으면 block 리스트의 그룹의 크기, 무지개블록의 갯수, 블록 기준 행, 열, 블록 번호를 append한다.
• BFS를 돌린 후, 블록 그룹이 형성된 게 하나라도 없으면 while문을 빠져나간다.
• block그룹이 여러 개라면 블록 그룹의 크기 -> 무지개 블록의 갯수 -> 블록 기준의 행 -> 열 각각 높은 순서로 정렬한 후 첫번째 인덱스의 있는 블록 그룹을 선택한다.
• 가장 큰 블록 그룹을 선택 했으면 블록의 갯수를 더하면서, 블록을 제거한다. 제거 시 -2값으로 변경한다. 
• 또한 블록의 갯수 * 블록의 갯수를 점수에 더해준다.
• 블록을 중력상태로 만들기 위해 행 n-2인덱스부터 위로 올라가면서 일반블록이거나 무지개 블록일때, 밑에 블록이 비어 있다면 fall() 함수를 통해 블록을 밑으로 이동할 수 있을만큼 옮긴다.
• 그후 zip()함수를 사용해 격자판을 반시계방향으로 돌린다.
• 다시 블록을 중력상태로 만들기 위해 행 n-2인덱스부터 위로 올라가면서 일반블록이거나 무지개 블록일때, 밑에 블록이 비어 있다면 fall() 함수를 통해 블록을 밑으로 이동할 수 있을만큼 옮긴다.

3. 문제 풀면서 느낀점

• 무지개블록은 어떤 일반 블록에도 낄 수 있어 블록 그룹에 들어갈 수 있으므로 방문처리를 할 때 배열형태로 하는 방법을 기억하자
• 블록 그룹의 기준 위치를 어렵게 구현했었는데, BFS를 돌릴 때 인덱스 접근을 0 ~ n-1, 0 ~ n-1 하므로 따로 기준위치 처리가 필요없이 블록그룹이 형성된 행,열 값을 기준위치로 삼으면 된다.
• 시계방향을 돌릴 땐 list(map(list, zip(*board[::-1])), 반시계방향을 돌릴 땐 list(map(list, zip(*board)))[::-1] 이다.. 꼭 기억하자

 

 

💻 소스코드

from collections import deque

n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(x, y, visited, b_num):
    q = deque()
    q.append((x, y))
    c = board[x][y]
    visited[x][y] = b_num
    size, r_n = 1, 0
    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:
                if board[nx][ny] == c and visited[nx][ny] == 0:
                    size += 1
                    visited[nx][ny] = b_num
                    q.append((nx, ny))
                elif board[nx][ny] == 0 and not b_num in visited[nx][ny]:
                    size += 1
                    r_n += 1
                    visited[nx][ny].append(b_num)
                    q.append((nx, ny))
    return size, r_n

def fall(x, y):
    stop = False
    for i in range(x+1, n):
        nx = i
        if board[nx][y] != -2:
            stop = True
            break
    if stop:
        board[nx-1][y] = board[x][y]
    else:
        board[nx][y] = board[x][y]
    board[x][y] = -2



score = 0
while True:
    visited = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if board[i][j] == 0:
                visited[i][j] = []

    b_num, block = 1, []
    for i in range(n):
        for j in range(n):
            if board[i][j] > 0 and visited[i][j] == 0:
                size, r_n = bfs(i, j, visited, b_num)
                if size > 1:
                    block.append([size, r_n, i, j, b_num])
                b_num += 1
    if len(block) == 0:
        break

    block.sort(key=lambda x:(-x[0], -x[1], -x[2], -x[3]))
    count = 0
    for i in range(n):
        for j in range(n):
            if board[i][j] > 0 and visited[i][j] == block[0][4]:
                count += 1
                board[i][j] = -2
            elif board[i][j] == 0 and block[0][4] in visited[i][j]:
                count += 1
                board[i][j] = -2

    score += (count*count)
    for i in range(n-2, -1, -1):
        for j in range(n):
            if board[i][j] >= 0 and board[i+1][j] == -2:
                fall(i, j)

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

    for i in range(n-2, -1, -1):
        for j in range(n):
            if board[i][j] >= 0 and board[i+1][j] == -2:
                fall(i, j)


print(score)