20058 - 마법사 상어와 파이어스톰

 

---

 

문제

https://www.acmicpc.net/submit/20058/63063274

로그인

 

풀이

해당 문제는 각 격자를 l의 값에 따라 잘 나누고, 접근해서 로직만 잘 수행하면 풀 수 있는 문제이다.

그 외에 배열 회전, 얼음 감소, 가장 큰 대륙 찾기등 부가적인 요소는 간단하게 해결할 수 있다.

 

l = 1

l = 2

 

 

예시를 보자.

 

n이 8, l이 1일때는 64 / 4 => 16개의 격자가 생긴다.

n이 8, l이 2일때는 64 / 16 => 4개의 격자가 생긴다.

이 값은 (2^n)^2 / (l^2)^2 라는 공식으로 얻을 수 있다.

 

이후에는 각 격자에 접근한다음에, 배열을 회전해줘야한다.

위와 같이 4군데에 접근해야하고 각 격자에 해당하는 부분만 탐색해야한다.

처음에 x, y는 0으로 시작하고 각 행과 열은 l^2만큼 돌아주면 된다.

 

첫번째 격자를 다 돌면 l^2 만큼 이동시켜준다음에 반복시켜 준다. 가로로 범위를 벗어날때는 x += l^2 를 해주고 밑의 격자로 이동시켜 준다.

 

나는 이런식으로 접근한다음에 임시2차원 배열을 만들어서 값을 복사한다음에, 회전시켜준다음, 원래위치에 넣어주는 식으로 반복했다.

 

이후 얼음을 까주는건 상하좌우 살펴봐서 카운트해주면 되고, 가장 큰 대륙은 bfs나 dfs, 뭐든지로 구해주면 된다.

 

코드

import copy
from sys import stdin
from collections import deque

def bfs(x, y):
    global dx, dy, board, n_size
    visited = [[False] * (n_size) for _ in range(n_size)]
    res = 0
    q = deque()
    visited[x][y] = True
    q.append((x, y))

    while q :
        x, y = q.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0<=nx<n_size and 0<=ny<n_size and not visited[nx][ny] and board[nx][ny] != 0:
                visited[nx][ny] = True
                q.append((nx, ny))

    for i in range(n_size):
        for j in range(n_size):
            if visited[i][j]: res +=1
    return res

def rotate(temp):
    return list(map(list, zip(*temp[::-1])))


# 초기화
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
n, q = map(int, input().split())
n_size = 2**n
board = [ list(map(int, stdin.readline().rstrip().split())) for _ in range(n_size) ]
l_list = list(map(int, stdin.readline().rstrip().split()))

for l in l_list :
    x, y = 0, 0
    l_size = 2**l
    
    # 격자 개수만큼 실행한다.
    for _ in range(n_size**2 // l_size**2):
        if y >= n_size:
            x += l_size
            y = 0
        temp = []
        for i in range(x, x + l_size):
            t = []
            for j in range(y, y + l_size):
                t.append(board[i][j])
            temp.append(t)
        temp = rotate(temp)

        k = m = 0
        for i in range(x, x + l_size):
            for j in range(y, y + l_size):
                board[i][j] = temp[k][m]
                m += 1
            k += 1
            m = 0
        y += 2**l


    # 각 칸들의 인접 얼음칸을 확인한다.
    t_board = copy.deepcopy(board)
    for i in range(n_size):
        for j in range(n_size):
            if t_board[i][j] == 0: continue

            cnt = 0
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]

                if 0<=nx<n_size and 0<=ny<n_size and t_board[nx][ny] != 0:
                    cnt +=1

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

# 합을 구한다.
answer = 0
for i in range(n_size):
    for j in range(n_size):
        answer += board[i][j]

maxSize = 0
# 가장 큰 대륙을 구한다.
for i in range(n_size):
    for j in range(n_size):
        if board[i][j] != 0:
            maxSize = max(bfs(i, j), maxSize)

print(answer)
print(maxSize)

 

후기

 

문제푸는도중 코드가 이상하더라도, 답을 맞추고 깔끔하게 리팩토링 해보자.