[삼성SW역량][Python/BOJ] 백준 20058 마법사 상어와 파이어스톰(구현+BFS)

 

간단하게 보면 

1. 얼음을 회전시키고 녹이는 함수 

2. 가장 큰 얼음 덩어리의 사이즈를 구하는 함수를 만들어 해결하면 된다.

 

 

 

문제는 얼음을 회전시키는 코드를 생각하기 쉽지않았다는 것이다. 

 

 

 

 

2^L씩 구간을 나누어 시계방향으로 90도 회전하는데 이  방법을 도저히!!! 생각이 나지 않았다.

이걸 매번 tmp로 받아서 저장하고 빼서 만드나? 너무 구차한데?

아닐것같은데 ? 만약 tmp로 안빼고 만들면 숫자가 움직이는 과정에서 원래 숫자를 덮어버려서 안될텐데?

 

 

 

정답은 바로 새롭게 저장할 mp배열을 만드는 거였다^-^! (정말 획기적!)

 

 

 

2^L 만큼의 간격으로 x,y를 넘어다니고

그 안에서는 i,j로 90도 시계방향으로 움직이도록 만든다. 

4중 for문으로 나타낸 그림은 아래 그림과 같다. 

 

 

 

코드 :

from collections import deque
from itertools import combinations as c 


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

def rotate_and_melt(mp, len_board, L) :
    
    # 회전한 board 저장용 
    new_mp = [[0]*(len_board) for i in  range(len_board)]
    
    
    # rotate 
    r_size = 2**L 
    for x in range(0,len_board,r_size) :
        for y in range(0,len_board, r_size) :
            for i in range(r_size):
                for j in range(r_size) :
                    # 90도로 회전 
                    new_mp[x+j][y+r_size-i-1] = mp[x+i][y+j]
    mp = new_mp
    melting_list= []
    # 녹일 얼음 찾기  
    for x in range(len_board) :
        for y in range(len_board) :
            ice_count = 0
            for dir in range(4) :
                nx,ny  = x + dx[dir], y + dy[dir]
                if 0<=nx<len_board and 0<=ny<len_board and mp[nx][ny] > 0:
                    ice_count+=1 
            if ice_count < 3 and mp[x][y] >0 :
                melting_list.append([x,y])


    # 저장된 얼음들 녹이기 
    for x,y in melting_list :
        mp[x][y] -=1 
    
    return mp 


def check_ice_bfs(mp,len_board) :
    vis = [[0]*(len_board) for i in range(len_board)]
    max_area_cnt = 0
    for x in range(len_board) :
        for y in range(len_board) :
            area_cnt = 0
            
            # 방문했거나 얼음이 없으면 continue 
            if vis[x][y] or mp[x][y] == 0 :
                continue 
            q = deque()
            q.append([x,y])
            vis[x][y] = 1 
            
            while q :
                cx,cy = q.popleft()
                area_cnt+=1 
                for i in range(4) :
                    nx,ny= cx + dx[i], cy+ dy[i]
                    if 0<=nx<len_board and 0<=ny<len_board and mp[nx][ny] >0 and vis[nx][ny]==0 :
                        vis[nx][ny] =1 
                        q.append([nx,ny])
            # 가장 큰 얼음 덩어리 찾기 
            max_area_cnt  = max(max_area_cnt, area_cnt)
            
            
    # 남아있는 얼음의 합 
    print(sum(sum(mp,[])))
    print(max_area_cnt)
            
    
    
    
if __name__=="__main__" :
    n,q = map(int,input().split())
    len_board = 2**n 
    mp = [list(map(int,input().split())) for i in range(len_board)]
    L_list = list(map(int,input().split()))
    
    for L in L_list :
        mp = rotate_and_melt(mp,len_board,L)
    
    check_ice_bfs(mp,len_board)