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

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

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

문제

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

파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. 이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다. (r, c)와 인접한 칸은 (r-1, c), (r+1, c), (r, c-1), (r, c+1)이다. 아래 그림의 칸에 적힌 정수는 칸을 구분하기 위해 적은 정수이다.

마법사 상어는 파이어스톰을 총 Q번 시전하려고 한다. 모든 파이어스톰을 시전한 후, 다음 2가지를 구해보자.

1. 남아있는 얼음 A[r][c]의 합
2. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

얼음이 있는 칸이 얼음이 있는 칸과 인접해 있으면, 두 칸을 연결되어 있다고 한다. 덩어리는 연결된 칸의 집합이다.

 

입력

첫째 줄에 N과 Q가 주어진다. 둘째 줄부터 2N개의 줄에는 격자의 각 칸에 있는 얼음의 양이 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

마지막 줄에는 마법사 상어가 시전한 단계 L1, L2, ..., LQ가 순서대로 주어진다.

 

출력

첫째 줄에 남아있는 얼음 A[r][c]의 합을 출력하고, 둘째 줄에 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다. 단, 덩어리가 없으면 0을 출력한다.

제한

• 2 ≤ N ≤ 6
• 1 ≤ Q ≤ 1,000
• 0 ≤ A[r][c] ≤ 100
• 0 ≤ Li ≤ N

풀이

삼성이 좋아하는 배열 회전이 또 들어가는 문제다. 전에 포스팅 한것 처럼 공식처럼 시계방향, 반시계방향정도는 외워두는게 편하다. 

어렵게 생각하면 한없이 어려울 테니 마음을 비우고 문제를 정확하게 이해하는게 중요...!

해야하는 것을 나눠보면 다음과 같다.

• 부분 격자를 시계방향으로 회전
• 얼음이 있는 칸과 3개이상 인접하지 못한 칸 얼음 녹이기
• 남은 얼음 중 가장 큰 덩어리 찾기

회전(rotate)

4중 포문이라니.. 교수님이 보시면 정말 화내시겠지만 어쩔 수 없었습니다..

격자를 2^L로 나누어 그 안에서 회전해야한다.

격자를 크게 돌 반복문을 2^L만큼 이동하도록 하고, 회전해야하는 격자 내부를 도는 반복문안에서 회전을 수행한다.

!!!! 공식처럼 외우기~~ !!!!

시계방향 90도 회전	new_arr[ n - 1 - j ][ i ] = arr[ i ][ j ]
반시계 방향 90도 회전	new_arr[ j ][ n - 1 - i ] = arr[ i ][ j ]

def rotate(arr, l):
    temp = [[0] * N for _ in range(N)]
    L = 2**l
    for ii in range(0, N, L):
        for jj in range(0, N, L):
            for i in range(L):
                for j in range(L):
                    temp[ii + i][jj + j] = arr[ii + (L-j-1)][jj + i]
    return temp

 

얼음 녹이기(melt_ice)

간단하게 인접한 칸 4개를 조사해서 3개 이상이면 그대로, 그 외일때 얼음을 하나 녹인다.

def melt_ice(arr):
    temp = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            ice_cnt = 0
            for d in range(4):
                nx = i + dx[d]
                ny = j + dy[d]
                if 0 <= nx < N and 0 <= ny < N:
                    if arr[nx][ny] > 0 :
                        ice_cnt += 1
            if ice_cnt < 3:
                temp[i][j] = game_map[i][j] - 1
            else:
                temp[i][j] = game_map[i][j]
    return temp

 

얼음 덩어리 찾기(bfs)

BFS알고리즘을 이용해 얼음덩어리를 찾는다. 가장 큰 얼음 덩어리를 찾야하기 때문에 완전탐색으로 모두 확인해야한다.

def bfs(x, y):
    q = deque()
    q.append([x,y])
    visited[x][y] = 1
    ice_cnt = 1
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < N and 0 <= ny <N:
                if visited[nx][ny] == 0 and game_map[nx][ny] > 0:
                    visited[nx][ny] = 1
                    q.append([nx, ny])
                    ice_cnt += 1
    return ice_cnt

 

코드

from collections import deque

n, q = map(int,input().split())
N = 2**n
game_map = [list(map(int, input().split())) for _ in range(N)]
l_list = list(map(int, input().split()))

def rotate(arr, l):
    temp = [[0] * N for _ in range(N)]
    L = 2**l
    for ii in range(0, N, L):
        for jj in range(0, N, L):
            for i in range(L):
                for j in range(L):
                    temp[ii + i][jj + j] = arr[ii + (L-j-1)][jj + i]
    return temp

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

def melt_ice(arr):
    temp = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            ice_cnt = 0
            for d in range(4):
                nx = i + dx[d]
                ny = j + dy[d]
                if 0 <= nx < N and 0 <= ny < N:
                    if arr[nx][ny] > 0 :
                        ice_cnt += 1
            if ice_cnt < 3:
                temp[i][j] = game_map[i][j] - 1
            else:
                temp[i][j] = game_map[i][j]
    return temp

def bfs(x, y):
    q = deque()
    q.append([x,y])
    visited[x][y] = 1
    ice_cnt = 1
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < N and 0 <= ny <N:
                if visited[nx][ny] == 0 and game_map[nx][ny] > 0:
                    visited[nx][ny] = 1
                    q.append([nx, ny])
                    ice_cnt += 1
    return ice_cnt


for i in range(q):

    game_map = rotate(game_map,l_list[i])
    game_map = melt_ice(game_map)

ice_group = []
ice_sum = 0
visited = [[0] * N for _ in range(N)]

max_ice = 0
for i in range(N):
    for j in range(N):
        if game_map[i][j] > 0:
            ice_sum += game_map[i][j]
            max_ice = max(max_ice, bfs(i,j))

print(ice_sum)
print(max_ice)