본문 바로가기
About/Algorithm

[백준 20058] 마법사 상어와 파이어스톰(Python 풀이)

김징어 2022. 1. 10. 23:30

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

 

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

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c

www.acmicpc.net

 

풀이

이번 문제는 배열의 회전, BFS를 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다.

우선 다음과 같이 입력을 받습니다.

N, Q = map(int, input().split(' ')) # N, Q
len_board = 2 ** N # 얼음을 저장할 보드의 길이
board = [list(map(int, input().split(' '))) for _ in range(len_board)] # 얼음 입력
L_list = list(map(int, input().split(' '))) # Level을 저장할 리스트

 

그 후 rotate_and_melting() 함수를 L_list의 원소 길이 만큼 수행합니다.

for L in L_list:
    board = rotate_and_melting(board, len_board, L)

 

rotate_and_melting() 함수는 격자를 Level에 따라 회전시키고, 얼음을 녹입니다.

먼저 격자를 Level에 따라 회전시킵니다.

이 문제에서 가장 어려운 부분은 Level에 따라 다르게 배열이 회전하는 부분인데, 다음과 같이 구현하였습니다.

new_board = [[0] * len_board for _ in range(len_board)] # 회전한 Board 저장 용

# rotate
r_size = 2 ** L # 격자 사이즈
for y in range(0, len_board, r_size): # 격자 시작 좌표 y축
    for x in range(0, len_board, r_size): # 격자 시작 좌표 x축
        for i in range(r_size): # 열 인덱스
            for j in range(r_size): # 행 인덱스
                new_board[y + j][x + r_size - i - 1] = board[y + i][x + j]

설명을 하자면, 우선 L=1인 경우에는 일반 배열 회전 알고리즘과 동일하게, 하나의 원소만 90도 이동하면 됩니다.

다만 회전 시킬 배열의 시작 좌표가 (0, 0)이 아니라 (y, x)라는 것을 명심해야합니다!! 따라서 (y + i, x + j)가 격자 시작 좌표로 부터 하나씩 원소를 가져오는 것이라는 입니다.

그림으로 나타내면 다음과 같습니다. 그림에 오타가 있네요 L=1 입니다.

하지만 L=1일 때만 생각하면 풀수 없고 L=2인 경우 부터 생각하여야 합니다.

설명하기가 쉽지는 않지만, 현재 격자의 N번째 열을  다음 격자의 N번째 행으로 바뀌도록 구성하면 됩니다. (90도 회전하기 때문) 이 때 N번째 열의 첫번째 원소는 N번째 행의 마지막 원소로, N번째 열의 마지막 원소는 N번째 원소의 첫번째 원소로 바뀌게 됩니다. (N번째 열 원소의 순서를 반전시키며 N번째 행으로 변환)

new_board[y + j][x + r_size - i - 1] = board[y + i][x + j]

그렇기 때문에 j는 행에 대한 인덱스지만, y축 좌표와 함께 움직이고, i는 열에 대한 인덱스이지만, x축 좌표와 함께 움직이도록 코드가 짜여집니다.  

N = 3, 4.. 아무리 커지더라도 현재 격자의 N번째 열을 다음 격자의 N번째 행 이라는 사실은 변하지 않습니다.

그 후 인근 좌표를 탐색하여 얼음을 녹입니다.

melting_list = [] # 녹을 얼음 좌표
for y in range(len_board):
    for x in range(len_board):
        ice_count = 0
        for d in range(len(dy)):
            ny = y + dy[d]
            nx = x + dx[d]

            if nx < 0 or ny < 0 or nx >= len_board or ny >= len_board:
                continue
            elif board[ny][nx] > 0:
                ice_count += 1

        if ice_count < 3 and board[y][x] != 0:
            melting_list.append((y, x))

# 저장된 얼음들을 녹임
for y, x in melting_list:
    board[y][x] -= 1

 

따라서 rotate_and_melting() 함수는 다음과 같이 구성되어 있습니다.

def rotate_and_melting(board, len_board, L):
    """
    Level에 맞게 회전 후 얼음을 녹임
    :param board: 보드
    :param len_board: 보드 길이
    :param L: level
    :return:
    """
    new_board = [[0] * len_board for _ in range(len_board)] # 회전한 Board 저장 용

    # rotate
    r_size = 2 ** L # 격자 사이즈
    for y in range(0, len_board, r_size): # 격자 시작 좌표 y축
        for x in range(0, len_board, r_size): # 격자 시작 좌표 x축
            for i in range(r_size): # 열 인덱스
                for j in range(r_size): # 행 인덱스
                    new_board[y + j][x + r_size - i - 1] = board[y + i][x + j]

    board = new_board
    melting_list = [] # 녹을 얼음 좌표
    for y in range(len_board):
        for x in range(len_board):
            ice_count = 0
            for d in range(len(dy)):
                ny = y + dy[d]
                nx = x + dx[d]

                if nx < 0 or ny < 0 or nx >= len_board or ny >= len_board:
                    continue
                elif board[ny][nx] > 0:
                    ice_count += 1

            if ice_count < 3 and board[y][x] != 0:
                melting_list.append((y, x))

    # 저장된 얼음들을 녹임
    for y, x in melting_list:
        board[y][x] -= 1

    return board

 

격자를 모두 회전하고, 얼음이 모두 녹았다면 이제 탐색을 합니다. check_ice_bfs() 함수를 호출하여 얼음의 상태를 파악한 후 정답을 출력합니다. 가장 큰 영역의 크기 또한 출력하여야하기 때문에 BFS 알고리즘을 이용하여 board를 탐색하고 얼음의 합과 최대 영역의 크기를 출력합니다.

def check_ice_bfs(board, len_board):
    """
    얼음 상태 확인
    :param board: 보드
    :param len_board: 보드 가로 길이
    :return:
    """
    used = [[False] * len_board for _ in range(len_board)]
    ice_sum = 0 # 얼음 합
    max_area_count = 0 # 영역 크기
    for y in range(len_board):
        for x in range(len_board):
            area_count = 0
            if used[y][x] or board[y][x] == 0:
                continue
            # BFS를 이용하여 얼음 덩어리 조사
            q = deque()
            q.append((y, x))
            used[y][x] = True

            while q:
                sy, sx = q.popleft()
                ice_sum += board[sy][sx] # 얼음 합 추가
                area_count += 1  # 얼음 카운트 추가

                for d in range(4):
                    ny = sy + dy[d]
                    nx = sx + dx[d]
                    if nx < 0 or ny < 0 or nx >= len_board or ny >= len_board or used[ny][nx]:
                        continue
                    if board[ny][nx] != 0:
                        used[ny][nx] = True
                        q.append((ny, nx))

            max_area_count = max(max_area_count, area_count) # 최대 얼음 덩어리 크기 파악

    print(ice_sum)
    print(max_area_count)

 

전체 소스 코드

from collections import deque

dy = (0, 1, 0, -1)
dx = (1, 0, -1, 0)

def rotate_and_melting(board, len_board, L):
    """
    Level에 맞게 회전 후 얼음을 녹임
    :param board: 보드
    :param len_board: 보드 길이
    :param L: level
    :return:
    """
    new_board = [[0] * len_board for _ in range(len_board)] # 회전한 Board 저장 용

    # rotate
    r_size = 2 ** L # 격자 사이즈
    for y in range(0, len_board, r_size): # 격자 시작 좌표 y축
        for x in range(0, len_board, r_size): # 격자 시작 좌표 x축
            for i in range(r_size): # 열 인덱스
                for j in range(r_size): # 행 인덱스
                    new_board[y + j][x + r_size - i - 1] = board[y + i][x + j]

    board = new_board
    melting_list = [] # 녹을 얼음 좌표
    for y in range(len_board):
        for x in range(len_board):
            ice_count = 0
            for d in range(len(dy)):
                ny = y + dy[d]
                nx = x + dx[d]

                if nx < 0 or ny < 0 or nx >= len_board or ny >= len_board:
                    continue
                elif board[ny][nx] > 0:
                    ice_count += 1

            if ice_count < 3 and board[y][x] != 0:
                melting_list.append((y, x))

    # 저장된 얼음들을 녹임
    for y, x in melting_list:
        board[y][x] -= 1

    return board

def check_ice_bfs(board, len_board):
    """
    얼음 상태 확인
    :param board: 보드
    :param len_board: 보드 가로 길이
    :return:
    """
    used = [[False] * len_board for _ in range(len_board)]
    ice_sum = 0
    max_area_count = 0
    for y in range(len_board):
        for x in range(len_board):
            area_count = 0
            if used[y][x] or board[y][x] == 0:
                continue
            # BFS를 이용하여 얼음 덩어리 조사
            q = deque()
            q.append((y, x))
            used[y][x] = True

            while q:
                sy, sx = q.popleft()
                ice_sum += board[sy][sx] # 얼음 합 추가
                area_count += 1  # 얼음 카운트 추가

                for d in range(4):
                    ny = sy + dy[d]
                    nx = sx + dx[d]
                    if nx < 0 or ny < 0 or nx >= len_board or ny >= len_board or used[ny][nx]:
                        continue
                    if board[ny][nx] != 0:
                        used[ny][nx] = True
                        q.append((ny, nx))

            max_area_count = max(max_area_count, area_count) # 최대 얼음 덩어리 크기 파악

    print(ice_sum)
    print(max_area_count)


def solve():
    N, Q = map(int, input().split(' '))
    len_board = 2 ** N
    board = [list(map(int, input().split(' '))) for _ in range(len_board)]
    L_list = list(map(int, input().split(' ')))

    for L in L_list:
        board = rotate_and_melting(board, len_board, L)

    check_ice_bfs(board, len_board)

solve()

Python3로 답안을 제출하면 시간초과가 나오고, PyPy3로 제출해야 통과가 되네요.
Python3으로 시간초과 안나오신 분은 알려주시면 감사드리겠습니다.

 

저작자표시

'About > Algorithm' 카테고리의 다른 글

[Programmers] 수식 최대화(Python 풀이) - 2020 카카오 인턴십 코딩테스트 문제  (0) 2022.01.19
[백준 8972] 미친 아두이노(Python 풀이)  (0) 2022.01.16
[백준 16985] Maaaaaaaaaze(Python 풀이)  (0) 2022.01.05
[백준 1202] 보석 도둑(C++ 풀이)  (0) 2022.01.03
[백준 4256] 트리 (C++ 풀이)  (0) 2021.12.27

'About/Algorithm' Related Articles

티스토리툴바