[백준 삼성기출 △] 마법사 상어와 파이어스톰(python)

이진규·2022년 10월 8일
1

백준(PYTHON)

목록 보기
96/115

문제

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

나의 코드

"""

"""

from copy import deepcopy
from collections import deque

N, Q = map(int, input().split())
pan = [ list(map(int, input().split())) for _ in range(2**N) ]
L = list(map(int, input().split()))

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

# 부분격자 나누고 배열을 시계방향으로 90도 회전하는 코드 + 얼음이 있는 칸과 3개 이상 근접하지 않으면 해당 칸의 얼음 양을 -1하는 코드
for l in L:
    if l == 0:
        pan2 = deepcopy(pan)
    else:
        for i in range(0, 2**N, 2**l): # ★ 부분 격자 나누기 + 시계방향 90도 회전
            for j in range(0, 2**N, 2**l):
                t = [ pan[k][j:j+2**l] for k in range(i, i+2**l) ]
                t = list(zip(*t[::-1]))

                for x in range(2**l):
                    for y in range(2**l):
                        pan[x+i][y+j] = t[x][y]
        pan2 = deepcopy(pan)

    # pan2는 복제본이고, 필수적임 -> 얼음의 양이 반복문이 도는중에 실시간으로 -1이 되면 결과값에 이상이 생김
    for i in range(2**N):
        for j in range(2**N):
            if pan2[i][j] > 0:
                cnt = 0 # 얼음이 있는 칸과 근접한 개수
                for k in range(4):
                    mx = i + dx[k]
                    my = j + dy[k]

                    if not (0 <= mx < 2**N and 0 <= my < 2**N):
                        continue

                    if pan2[mx][my] > 0:
                        cnt += 1

                if cnt < 3:
                    pan[i][j] -= 1


# 남아있는 얼음의 합을 구하는 코드
def ice_sum():

    ice_amount = 0
    for i in range(2**N):
        for j in range(2**N):
            if pan[i][j] > 0:
                ice_amount += pan[i][j]

    return ice_amount

# 남아있는 얼음 중 가장 큰 덩어리가 차지하는 개수를 구하는 코드
def ice_big(x, y):
    visited[x][y] = True
    cnt = 1
    q = deque([(x, y)])

    while q:
        px, py = q.popleft()

        for k in range(4):
            mx = px + dx[k]
            my = py + dy[k]

            if (0 <= mx < 2**N and 0 <= my < 2**N):
                if pan[mx][my] > 0 and not visited[mx][my]:
                    visited[mx][my] = True
                    cnt += 1
                    q.append((mx, my))

    return cnt


print(ice_sum()) # 남아있는 얼음의 합

answer = 0
visited = [ [False] * (2**N) for _ in range(2**N) ]
for i in range(2**N): # 남아있는 얼음 중 가장 큰 덩어리가 차지하는 개수
    for j in range(2**N):
        if pan[i][j] > 0:
            answer = max(answer, ice_big(i, j))

print(answer)


    

설명

배열의 시계방향 90도 회전 + BFS 탐색에 대한 문제

참고 자료

https://velog.io/@mmy789/Python-zip-%EC%9D%B4%EC%9A%A9%ED%95%B4%EC%84%9C-2%EC%B0%A8%EC%9B%90-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%ED%9A%8C%EC%A0%84%ED%95%98%EA%B8%B0#1-%EC%8B%9C%EA%B3%84-%EB%B0%A9%ED%96%A5%EC%9C%BC%EB%A1%9C-%ED%9A%8C%EC%A0%84

profile
항상 궁금해하고 공부하고 기록하자.

0개의 댓글