[python] BOJ 백준 20058: 마법사상어와 파이어스톰

1. 문제  

마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 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. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수

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

2. 입력   

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

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

3. 출력   

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

4. 해결방법   

이 문제는 구현, 시뮬레이션, BFS 문제이다. 격자를 나눠서 회전시키는 함수, 얼음양을 줄어들게 하는 함수, 얼음덩어리를 세는 함수 3가지로 구현하였다. 단계를 돌면서 divide와 reduce함수를 실행시키고, 마지막에 얼음덩어리의 최대 개수를 구하면서 bfs함수를 써주면된다.  

1) divide 함수: 격자의 길이는 2의 단계계수 제곱이다. 행, 열에 대해서 격자의 길이만큼 증가시키면서 임시배열을 만들어주고, 그 임시배열을 회전시킨후 원배열에 할당해주면된다. 회전시킬때는 zip함수를 이용하면 한줄로 구현할 수 있다. 

2) reduce 함수: 모든 좌표에 대해서 상하좌우를 탐색하며 인접한 칸중에 얼음이 존재하는 칸이 몇개인지 세주고, 갯수가 2이하라면 원배열에서 1을 빼주면된다. 하지만 여기서 주의할 점은, 원배열에 바로 적용을 하면 동시에 얼음의 양이 줄어드는 것이 아닌 순차적으로 줄어들게 되는 것이므로 임시배열에 할당을 해놓고, 나중에 적용을 해야한다. 

3) bfs함수: 얼음덩어리를 세기 위하여 큐에 좌표를 저장하고, 상하좌우로 탐색하면서 얼음이 있으면 큐에 또 저장하면서 탐색을 진행하면된다. 단, 방문집합을 하나 생성해서 한번 방문한 곳은 다시 방문하지 않도록 해야한다. 

5) 구현코드   

from collections import deque
n,q=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(2**n)] #얼음배열 
command=list(map(int,input().split())) #L단계 
visited=set() #얼음덩어리 방문배열 
#인접 네방향 
dx=[0,0,1,-1]
dy=[1,-1,0,0]
length=2**n #배열의 길이 

#격자나눠서 회전시키기 
def divide(a,c):
  cnt=2**c #격자의 길이 
  for i in range(0,length,cnt):
    for j in range(0,length,cnt):
      temp=[] #격자임시배열 
      for k in range(cnt):#격자의 길이만큼
        temp.append(a[i+k][j:j+cnt]) #임시배열만들기 
      temp=list(zip(*temp[::-1])) #90도회전 
      for k in range(cnt):
        a[i+k][j:j+cnt]=temp[k] #원래배열에 반영 
  return a

#얼음양 줄어들기 
def reduce(a):
  temp=[[0]*length for _ in range(length)] #임시배열 
  for i in range(length):
    for j in range(length):
      cnt=0 #인접한 칸중 얼음이있는개수 
      for d in range(4):#네방향 탐색 
        nx,ny=i+dx[d],j+dy[d]
        if 0<=nx<length and 0<=ny<length:
          if a[nx][ny]>0: #인접하고 얼음있으면
            cnt+=1 #카운트증가 
      if cnt<=2 and a[i][j]>0: #카운트 2이하 
        temp[i][j]-=1 #임시배열에 반영 
  for i in range(length):
    for j in range(length):
      a[i][j]+=temp[i][j] #원배열에 반영 
  return a

#얼음덩어리 개수세기 
def bfs(x,y):
  q=deque()
  q.append((x,y))#큐에 저장 
  visited.add((x,y))#방문
  cnt=1 #덩어리 개수 
  while q:
    x,y=q.popleft()
    for i in range(4): #네방향 탐색하면서 
      nx,ny=x+dx[i],y+dy[i] 
      #범위안에 있고 
      if 0<=nx<length and 0<=ny<length:
        #방문하지 않았고 0이 아니면 
        if (nx,ny) not in visited and a[nx][ny]!=0:
          q.append((nx,ny)) #큐에 저장 
          visited.add((nx,ny)) #방문처리
          cnt+=1 #덩어리개수증가 
  return cnt 
  
#단계 실행 
for c in command:
  a=divide(a,c)
  a=reduce(a)

answer=0 
max_ans=0
for i in range(length):
  for j in range(length):
    if a[i][j]>0:
      answer+=a[i][j] #누적합
      max_ans=max(max_ans,bfs(i,j)) #덩어리최대값
print(answer)
print(max_ans)

 

⭐️난이도:  골드 4 ⭐️

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

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