143. [삼성기출39]Python 백준 21609 상어 중학교

안녕하세요 코딩하는 덕구입니다.

파이썬 백준 21609 상어 중학교 입니다.

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

21609번: 상어 중학교

 

요즘 코테 문제를 풀면서 느끼는 건 알고리즘이나 구현의 난이도보다 문제를 바르게 읽고 바르게 구현하는

독해력과 논리적으로 부족함 없이 꼼꼼하게 구현하는 섬세함이 더 요구되는 것 같다.

 

문제 접근

1. 블럭 그룹 찾기

- 격자를 처음부터 끝까지 탐색합니다.

- 만약 아직 방문하지 않고 일반 블럭이라면 bfs를 이용해 블럭 그룹을 찾습니다.

이때 무지개 블럭은 블럭 그룹 크기를 구하기 위해서 방문처리를 잠시 했다가. 방문 처리를 취소합니다.

더 큰 다른 블럭 그룹에 무지개 블럭이 포함될 수 있기 때문.

블럭 그룹 후보를 찾았다면 후보 리스트에 [블럭 크기, 무지개 블럭 개수, 좌표] 를 넣어 추가합니다.

모든 블럭 그룹 후보를 찾은 후 후보 리스트를 조건에 맞게 정렬 하여 최우선 순위의 후보를 뽑아

해당 블럭 그룹을 제거합니다.

 

2. 블럭 그룹 제거

대표 블럭에서 bfs를 돌려 제거해줍니다.

 

3. 중력

격자 맨 밑 한칸 위 에서 부터  맨 위 순서로 탐색합니다.

초기 loc은 탐색 위치의 한칸 아래 방향입니다.

만약 [loc-1]에 일반 블럭이 있다면 loc이 빈칸인지 확인 후 빈칸이라면 [loc-1] 블럭을 loc에 내립니다.

이후 loc을 1씩 증가시키며 반복합니다.

def gravity():
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] not in [-2, -1]:
                loc = i + 1
                while loc < N:
                    if board[loc][j] == -2:
                        if board[loc - 1][j] not in [-2, -1]:
                            board[loc][j] = board[loc - 1][j]
                            board[loc - 1][j] = -2
                    loc += 1
    return

 

4. 회전

1 2 3                                3 6  9

4 5 6                               2 5  8

7 8 9                               1  4  7

회전 전의 1번째 행의 맨 마지막 자료 = 회전 후 1 행의 맨 1 번째 자료

회전 전의 2번째 행의 맨 마지막 자료 = 회전 후 1 행의 맨 2 번째 자료

회전 전의 3번째 행의 맨 마지막 자료 = 회전 후 1 행의 맨 3 번째 자료

 

회전 전의 1번째 행의 2번째 자료 = 회전 후 2 행의 맨 1 번째 자료

회전 전의 2번째 행의 2번째 자료 = 회전 후 2 행의 맨 2 번째 자료

회전 전의 3번째 행의 2번째 자료 = 회전 후 2 행의 맨 3 번째 자료

즉 행을 위에서 아래로 접근하여 각 행의 마지막에서 앞의 순서로 1개씩 뽑아 새로운 행으로 정리하면 왼쪽 회전이 됩니다.

 

board = [[row[i] for row in board] for i in range(N-1, -1, -1)]

 

5. 중력

3번과 같습니다.

 

Python 정답 코드

백준 21609 상어 중학교 코드입니다. 설명은 아래에 있습니다.

 

 

from collections import deque
N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[False for _ in range(N)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def bfs(i, j):
    global visited
    rainbow = []
    q = deque()
    q.append([i, j])
    block_size = 1
    rainbow_size = 0
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = dx[d] + x, dy[d] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny]:
                    if board[nx][ny] == board[i][j]:
                        q.append([nx, ny])
                        visited[nx][ny] = True
                        block_size += 1

                    elif board[nx][ny] == 0:
                        q.append([nx, ny])
                        visited[nx][ny] = True
                        block_size += 1
                        rainbow_size += 1
                        rainbow.append([nx, ny])
    for r in rainbow:
        x, y = r
        visited[x][y] = False
    return block_size, rainbow_size

def gravity():
    for i in range(N-2, -1, -1):
        for j in range(N):
            if board[i][j] not in [-2, -1]:
                loc = i + 1
                while loc < N:
                    if board[loc][j] == -2:
                        if board[loc - 1][j] not in [-2, -1]:
                            board[loc][j] = board[loc - 1][j]
                            board[loc - 1][j] = -2
                    loc += 1
    return

def rotate():
    global board
    board = [[row[i] for row in board] for i in range(N-1, -1, -1)]
    return

def delete(i, j):
    color = board[i][j]
    board[i][j] = -2
    q = deque()
    q.append([i, j])
    block_size = 1
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = dx[d] + x, dy[d] + y
            if 0 <= nx < N and 0 <= ny < N:
                if (board[nx][ny] == color) or (board[nx][ny] == 0):
                    q.append([nx, ny])
                    board[nx][ny] = -2
                    visited[nx][ny] = True #무지게 블록 방문처리
                    block_size += 1
    return block_size**2


def solve():
    global visited
    score = 0
    cnt = 0
    while True:
        cnt += 1
        max_block = 0
        visited = [[False for _ in range(N)] for _ in range(N)]
        candidate = []
        for i in range(N):
            for j in range(N):
                if not visited[i][j] and board[i][j] not in [-2, -1, 0]:
                    visited[i][j] = True
                    block_size, rainbow_size = bfs(i, j)
                    if block_size >= 2:
                        candidate.append([block_size, rainbow_size, i, j])
                        max_block = max(max_block, block_size)
        if max_block < 2:
            break
        candidate.sort(key=lambda x:[-x[0], -x[1], -x[2], -x[3]])
        _, _, i, j = candidate[0]
        score += delete(i, j)
        gravity()
        rotate()
        gravity()
    return score

print(solve())

 

Python 코드 설명

 

격자를 탐색하며 2 이상인 블럭 그룹을 candidate에 추가합니다.

블럭 그룹 크기가 2 이상인 그룹이 존재하면 후보를 우선순위에 맞게 정렬한 후

해당 블럭 그룹을 지우면서 점수를 증가시키고 중력, 회전, 중력을 반복합니다.

def solve():
    global visited
    score = 0
    cnt = 0
    while True:
        cnt += 1
        max_block = 0
        visited = [[False for _ in range(N)] for _ in range(N)]
        candidate = []
        for i in range(N):
            for j in range(N):
                if not visited[i][j] and board[i][j] not in [-2, -1, 0]:
                    visited[i][j] = True
                    block_size, rainbow_size = bfs(i, j)
                    if block_size >= 2:
                        candidate.append([block_size, rainbow_size, i, j])
                        max_block = max(max_block, block_size)
        if max_block < 2:
            break
        candidate.sort(key=lambda x:[-x[0], -x[1], -x[2], -x[3]])
        _, _, i, j = candidate[0]
        score += delete(i, j)
        gravity()
        rotate()
        gravity()
    return score

 

 상하좌우를 탐색하며 블럭색이 같거나 0 이면 block_size를 1 증가시키고 q에 넣습니다.

이때 탐색하는 블럭이 무지개(0)라면 rainbow_size를 증가시키고, rainbow 리스트에 추가합니다.

탐색이 끝난 후 무지개 블럭은 방문처리를 취소하고 block_sized와 rainbow_size를 return 합니다.

def bfs(i, j):
    global visited
    rainbow = []
    q = deque()
    q.append([i, j])
    block_size = 1
    rainbow_size = 0
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = dx[d] + x, dy[d] + y
            if 0 <= nx < N and 0 <= ny < N:
                if not visited[nx][ny]:
                    if board[nx][ny] == board[i][j]:
                        q.append([nx, ny])
                        visited[nx][ny] = True
                        block_size += 1

                    elif board[nx][ny] == 0:
                        q.append([nx, ny])
                        visited[nx][ny] = True
                        block_size += 1
                        rainbow_size += 1
                        rainbow.append([nx, ny])
    for r in rainbow:
        x, y = r
        visited[x][y] = False
    return block_size, rainbow_size

백준 21609 상어 중학교 Python 코드였습니다.

감사합니다.