[Python] n20058) 마법사 상어와 파이어스톰

이 문제는 회전(90도), 인접한 얼음구하기, BFS를 구현할 수 있어야 하는 문제이다.

맵 크기 : 2^N X 2^N

얼음의 양 : A[r][c]

단계 : L

 

파이어스톰 단계

1) 격자(2^N X 2^N)를 부분격자2^L X 2^L로 나눈다.

2) 모든 부분 격자들을 시계방향으로 90도 회전시킨다.

3) 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.

 

우리가 출력해야 하는 것은?

1) 남아 있는 얼음 A[r][c]의 합

2) 남아 있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 (단, 덩어리가 없으면 0을 출력)

 

** 제한 **

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

 

 

단계 1) 회전

왼쪽 상단 -> 오른쪽 상단 -> 왼쪽 하단 -> 오른쪽 하단 순

1) 왼쪽 상단

x=0, y=0, i=0 

# tmp, map_list 순

1 : (0,0) -> (0,3), j=0 

2 : (0,1) -> (1,3), j=1

3 : (0,2) -> (2,3), j=2

4 : (0,3) -> (3,3), j=3

 

x=0 ,y=0 ,i=1

9: (1,0) -> (0,2), j=0

10 : (1,1) -> (1,2), j=1

11 : (1,2) -> (2,2), j=2

12 : (1,3) ->(3,2), j=3

 

2) 왼쪽 하단

x=0, y=4, i=0

5: (0,4) -> (0,7)

6: (0,5) -> (1,7)

7:  (0,6) -> (2,7)

8:  (0,7) -> (3,7)

 

 

3) 오른쪽 하단

x=4, y=4,i=0

37 : (4,4) -> (4,7)

38 : (4,5) -> (5,7)

39 : (4,6) -> (6,7)

40 : (4,7) -> (7,7)

 

x=4, y=4, i=1

45 : (5,4) -> (4,6) 

46 : (5,5) -> (5,6)

47 : (5,6) -> (6,6)

48 : (5,7) -> (7,6)

 

 

x=0, y=0일때 map_list[&&][**] **에는 4~1이 들어간다.

x=0,y=L일땐, 7~4가 들어간다.

x=L, y=0일땐, 4~1

x=L,y=L일땐, 7~4

 

즉 **은 y 값과 i 값에 의해 변화가 일어난다.

&&은 x값과 j값에 의해 변화가 일어난다.

 

map_list[x+j][L+y-i-1]=tmp[i+x][j+y]

 

---

단계2) 인접한 얼음이 3개 또는 그 이상과 인접해있지 않은 칸의 얼음의 양을 1 줄이기

인접과 관련된 문제는 방향 벡터를 사용한다.

예를 들어 상하좌우인 경우,

(-1,0), (1,0), (0,-1), (0,1)이니까

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

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

 

 

---

단계3) 남아있는 얼음 A[r][c]의 합과, 가장 큰 덩어리가 차지하는 칸의 개수 출력하기

(단, 덩어리가 없으면 0 출력하기)

 

---

 

L=1

2 X 2 (부분격자 크기)

 

L=2

2^2 X 2^2

 

from collections import deque
from copy import deepcopy

_N, Q = map(int, input().split())
N = pow(2, _N)
map_list = []
map_list = [list(map(int, input().split())) for _ in range(N)]
L_list = list(map(int, input().split()))

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

# 단계 1. 회전
# 단계 2. 인접한 얼음 구하기
# 단계 3. 전체합 구하기

# tmp라는 복사본 리스트를 이용해서, 변경된 결과를 전체 맵에 넣어주는 작업.
# 왜냐하면 전체맵 하나로 작업하게 되면, 변경전 값을 불러올 수 없어서, 작업이 꼬이게 되기 때문

# 단계 1. 회전
for l in L_list:
    L = pow(2, l)
    tmp = deepcopy(map_list)
    for x in range(0, N, L):  # 부분격자 행
        for y in range(0, N, L):  # 부분격자 열
            for i in range(L):  # 행
                for j in range(L):  # 열
                    map_list[x + j][L + y - i - 1] = tmp[i + x][j + y]
    tmp = deepcopy(map_list)

    # 단계2 인접한 얼음을 연속해서 찾아내야 한다.
    for n in range(N):
        for m in range(N):
            if tmp[n][m] == 0:
                continue
            cnt = 0
            for k in range(4):
                x = n + dx[k]
                y = m + dy[k]
                if y<0 or y>=N or x<0 or x>=N:
                    continue
                if map_list[x][y] != 0:
                    cnt += 1
            if cnt < 3:
                tmp[n][m] -= 1
    map_list = deepcopy(tmp)

# 단계3
# BFS는 너비 우선 탐색이라고 부르며, 가까운 노드부터 우선적으로 탐색하는 알고리즘, 최단경로
# 큐 자료구조를 이용함 (방문 기준 : 번호가 낮은 인접 노드부터)
total = 0
max_ice = 0

for i in range(N):
    for j in range(N):
        if map_list[i][j] == 0:
            continue
        queue = deque()
        queue.append((i, j))
        total += map_list[i][j]
        map_list[i][j] = 0
        cnt = 0
        while len(queue) != 0:
            cx, cy = queue.popleft()  # y가 행, x가 열
            cnt += 1
            for k in range(4):
                x = cx + dx[k]
                y = cy + dy[k]
                if y < 0 or y >= N or x < 0 or x >= N or map_list[x][y] == 0:
                    continue
                queue.append((x, y))
                total += map_list[x][y]
                map_list[x][y] = 0

        max_ice = max(max_ice, cnt)

print("{}\n{}".format(total, max_ice))

---

참고 출처

github.com/tony9402/baekjoon/tree/main/solution/simulation

tony9402/baekjoon

문제 

www.acmicpc.net/problem/20058

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