[백준, 삼성 기출] 20058_마법사 상어와 파이어스톰 (Python)

20058_마법사 상어와 파이어스톰 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 20058번: 마법사 상어와 파이어스톰

1. 기록

• 22/04/22 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> n을 입력받는다. -> 2^n = 행의 갯수, 열의 갯수
>> 인접해있는 얼음칸의 갯수가 3개 이상인지 어떻게 판단하는게 좋을지?
>> 모두 돌아서 3개미만인 칸의 좌표를 append해주자.
>> 이후 해당 좌표의 얼음을 -1 해준다. 얼음이 바깥쪽부터 안쪽으로 파고드는형태로 녹을 것임.

# 파이어 스톰 시전
>> 파이어 스톰에 해당하는 격자의 크기 만큼 쪼갠다. -> how?
>> for i in range(0, m, 2^k) (시전한 숫자의 지수승 값만큼 이동)
>>  for j in range(0, m, 2^k)

>> 해당 격자를 90도 만큼 시계방향으로 돌린다. [i,j] -> [j, (n-1)-i]
>> 시계 방향으로 돌린 격자를 다른 map 등에 저장하고 다시 graph에 할당하는 식으로 한다.


2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from pprint import pprint
from collections import deque

# n, q 를 입력 받는다.
n, q = map(int, input().split())
m = 2**n

# graph 를 입력받는다.
graph = list(list(map(int,input().split())) for _ in range(m))

# 마법 사이즈를 입력받는다.
magics = deque(list(map(int, input().split())))
m = 2**n

# 주변 얼음갯수를 카운트해주는 함수
def ice3(x,y, ice_cnt):
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 범위에 벗어나지 않으면서 인접 위치에 얼음이 있으면
        if 0 <= nx < m and 0 <= ny < m and graph[nx][ny] >= 1 and graph[x][y] >= 1:
            ice_cnt[x][y] += 1

    return ice_cnt

# 마법 끝날때 까지
while magics:

    # k는 지수승할 숫자
    k = magics.popleft()
    s = 2 ** k

    # map = [[0] * m for _ in range(m)]
    # 격자를 나누고 시계방향으로 90도 회전시킨다.
    for x in range(0, m, s):
        for y in range(0, m, s):
            tmp = [graph[i][y:y+s] for i in range(x, x+s)]
            print(f"tmp입니다. {tmp}")
            for i in range(s):
                for j in range(s):
                    graph[x + j][y + s - 1 - i] = tmp[i][j]

    # 주변 얼음 갯수를 카운트 해준다.
    ice_cnt = [[0] * m for _ in range(m)]
    dx = [0, -1, 0, 1]
    dy = [-1, 0, 1, 0]
    for x1 in range(m):
        for y1 in range(m):
            ice3(x1,y1, ice_cnt)

    # 조건에 만족하지않는 얼음의 갯수를 -1 해준다.
    for x2 in range(m):
        for y2 in range(m):
            if ice_cnt[x2][y2] >= 0 and ice_cnt[x2][y2] < 3:
                if graph[x2][y2] >= 1:
                    graph[x2][y2] -= 1


# graph에 있는 얼음의 갯수와 최대 얼음덩어리의 칸의 갯수를 세어준다.
total_ice = 0

for i in range(m):
    for j in range(m):
        total_ice += graph[i][j]

def last(x, y, visited, max_mass, mass):
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    while q:
        x, y = q.popleft()
        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<m and 0<=ny<m and visited[nx][ny] == False and graph[nx][ny] >= 1:
                visited[nx][ny] = True
                q.append((nx, ny))
                mass += 1
    return mass

visited = [[False]*m for _ in range(m)]
max_mass = 0

for i in range(m):
    for j in range(m):
        if graph[i][j] > 0 :
            mass = 1
            mass = last(i, j, visited, max_mass, mass)
            if max_mass < mass:
                max_mass = mass

print(total_ice)
print(max_mass)

(4) 정리

이 문제에서 가장 어려운 부분은
원하는 격자만큼 어떻게 쪼갤 것인가 ★
쪼갠 격자를 어떻게 90도 만큼 시계방향으로 회전시킬 것인가 이다. ★
무려 4중 for문을 이용해야한다.
시험에서 이 방법을 어떻게 생각할지 의문이다.
문제 읽고 문제풀이 코드 이해하는데까지 4시간 걸렸다.
다음 사진으로 핵심 부분을 이해하시면 좋을 듯하다.

90도 시계방향으로 회전하는 로직 이해하기

격자로 쪼개고 90도 시계방향으로 회전하는 로직

(5) 참고

참고 풀이