141. [삼성기출37]Python 백준 20058 마법사 상어와 파이어스톰

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

파이썬 백준 20058 마법사 상어와 파이어스톰 입니다.

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

20058번: 마법사 상어와 파이어스톰

 

문제 접근

 

def solve():
    for l in L:
        rotate(l)
        melt()

    ans1, ans2 = block()
    print(ans1)
    print(ans2)

solve()

구현 문제라고 생각합니다. L번 동안 규칙에 맞게 회전 시키고, 녹이는 함수를 작성했습니다.

 

격자의 회전을 구현하는 코드입니다.

1, 2 라인의 for문은 회전하는 모든 부분 격자의 왼쪽 위의 좌표를 접근합니다.

3번 라인의 for문은 각 부분 격자의 가장 바깥쪽 테두리부터 시작해서

안쪽 테두리까지 회전시키기 위해 접근합니다.

부분격자의 가장 바깥쪽 테두리의 가장 왼쪽 위 좌표를 (x, y) 라고 하면

그 다음 단계는 (x + 1, y + 1)

그 다음 단계는 (x + 2, y + 2)

(x + stage, y + stage)

for start_x in range(0, 2**N, 2**l):
    for start_y in range(0, 2**N, 2**l):
        for stage in range(0, (2**l)//2, 1):
            stage_length = 2**l - stage*2
            for i in range(stage_length):

 

 

Python 정답 코드

백준 20058 마법사 상어와 파이어스톰 파이썬 코드입니다. 설명은 아래에 있습니다.

 

from collections import deque
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(2**N)]
L = list(map(int, input().split()))
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def rotate(l):
    for start_x in range(0, 2**N, 2**l):
        for start_y in range(0, 2**N, 2**l):
            for stage in range(0, (2**l)//2, 1):
                stage_length = 2**l - stage*2

                stage_x, stage_y = start_x + stage, start_y + stage
                left_edge = [board[stage_x + stage_length - 1 - i][stage_y] for i in range(stage_length)]
                down_edge = [board[stage_x + stage_length - 1][stage_y + i] for i in range(stage_length)]
                right_edge = [board[stage_x + stage_length - 1 - i][stage_y + stage_length - 1] for i in range(stage_length)]
                up_edge = [board[stage_x][stage_y + i] for i in range(stage_length)]

                for i in range(stage_length):
                    #회전 후 윗면
                    board[stage_x][stage_y + i] = left_edge[i]
                    #회전 후 밑면
                    board[stage_x + stage_length - 1][stage_y + i] = right_edge[i]
                    #회전 후 왼쪽
                    board[stage_x + i][stage_y] = down_edge[i]
                    #회전 후 오른 쪽
                    board[stage_x + i][stage_y + stage_length - 1] = up_edge[i]

def debug():
    for i in range(2**N):
        for j in range(2**N):
            print(board[i][j], end=" ")
        print()
    print()

def melt():
    melt_list = []
    for i in range(2**N):
        for j in range(2**N):
            cnt = 0
            for d in range(4):
                nx, ny = dx[d] + i, dy[d] + j
                if 0 <= nx < 2**N and 0 <= ny < 2**N:
                    if board[nx][ny] != 0:
                        cnt += 1
            if cnt < 3:
                if board[i][j] != 0:
                    melt_list.append([i, j])

    for m in melt_list:
        x, y = m
        board[x][y] -= 1

def block():
    ans1 = 0
    ans2 = 0
    visited = [[False for _ in range(2**N)] for _ in range(2**N)]
    q = deque()
    for i in range(2**N):
        for j in range(2**N):
            if not visited[i][j] and board[i][j] != 0:
                visited[i][j] = True
                ans1 += board[i][j]
                size = 1
                q.append([i, j])
                while q:
                    x, y = q.popleft()
                    for d in range(4):
                        nx, ny = dx[d] + x, dy[d] + y
                        if 0 <= nx < 2**N and 0 <= ny < 2**N:
                            if not visited[nx][ny]:
                                if board[nx][ny] != 0:
                                    visited[nx][ny] = True
                                    size += 1
                                    ans1 += board[nx][ny]
                                    q.append([nx, ny])
                ans2 = max(ans2, size)
    return [ans1, ans2]

def solve():
    for l in L:
        rotate(l)
        melt()

    ans1, ans2 = block()
    print(ans1)
    print(ans2)

solve()

Python 코드 설명

L번동안 주어진 조건에 맞게 회전 후, 조건에 맞게 녹였습니다.

L번의 순서가 끝난 후 얼음의 합(ans1)과, 가장 큰 덩어리가 차지하는 칸의 개수(ans2)를 출력합니다.

def solve():
    for l in L:
        rotate(l)
        melt()

    ans1, ans2 = block()
    print(ans1)
    print(ans2)

 

회전하는 함수 rotate 입니다.

1, 2번 라인에서는 부분격자의 첫 좌표에 접근

3번 라인에서는 각 부분격자의 바깥쪽 사각형부터 시작해서 안쪽 사각형까지 

시작 좌표 x, y에 stage를 더 해줘 접근합니다.

이후 해당 정보들을 바탕으로 단계별 사각형의 상, 하, 좌, 우 정보를 입력받고

회전시키면 이동할 곳에 대입합니다.

def rotate(l):
    for start_x in range(0, 2**N, 2**l):
        for start_y in range(0, 2**N, 2**l):
            for stage in range(0, (2**l)//2, 1):
                stage_length = 2**l - stage*2

                stage_x, stage_y = start_x + stage, start_y + stage
                left_edge = [board[stage_x + stage_length - 1 - i][stage_y] for i in range(stage_length)]
                down_edge = [board[stage_x + stage_length - 1][stage_y + i] for i in range(stage_length)]
                right_edge = [board[stage_x + stage_length - 1 - i][stage_y + stage_length - 1] for i in range(stage_length)]
                up_edge = [board[stage_x][stage_y + i] for i in range(stage_length)]

                for i in range(stage_length):
                    #회전 후 윗면
                    board[stage_x][stage_y + i] = left_edge[i]
                    #회전 후 밑면
                    board[stage_x + stage_length - 1][stage_y + i] = right_edge[i]
                    #회전 후 왼쪽
                    board[stage_x + i][stage_y] = down_edge[i]
                    #회전 후 오른 쪽
                    board[stage_x + i][stage_y + stage_length - 1] = up_edge[i]

 

녹이는 함수입니다.

상하좌우만 확인해서 주변에 얼음이 3개이상 없다면 현재 위치의 얼음을 녹이는 간단한 함수입니다.

애초에 얼음이 없다면 제외

def melt():
    melt_list = []
    for i in range(2**N):
        for j in range(2**N):
            cnt = 0
            for d in range(4):
                nx, ny = dx[d] + i, dy[d] + j
                if 0 <= nx < 2**N and 0 <= ny < 2**N:
                    if board[nx][ny] != 0:
                        cnt += 1
            if cnt < 3:
                if board[i][j] != 0:
                    melt_list.append([i, j])

    for m in melt_list:
        x, y = m
        board[x][y] -= 1

 

정답을 구하기 위한 함수 block입니다.

얼음의 양과 최대 크기를 bfs를 이용해 탐색 후 출력합니다.

def block():
    ans1 = 0
    ans2 = 0
    visited = [[False for _ in range(2**N)] for _ in range(2**N)]
    q = deque()
    for i in range(2**N):
        for j in range(2**N):
            if not visited[i][j] and board[i][j] != 0:
                visited[i][j] = True
                ans1 += board[i][j]
                size = 1
                q.append([i, j])
                while q:
                    x, y = q.popleft()
                    for d in range(4):
                        nx, ny = dx[d] + x, dy[d] + y
                        if 0 <= nx < 2**N and 0 <= ny < 2**N:
                            if not visited[nx][ny]:
                                if board[nx][ny] != 0:
                                    visited[nx][ny] = True
                                    size += 1
                                    ans1 += board[nx][ny]
                                    q.append([nx, ny])
                ans2 = max(ans2, size)
    return [ans1, ans2]

백준 20058 마법사 상어와 파이어스톰 Python 코드였습니다.

감사합니다.