본문 바로가기

개발/algorithm

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

문제 링크

 

풀이 

디버깅 정말 ... 힘들었다.

첫번째는 90도 회전시키는 것이 올바르게 구현되지 않아 힘들었다. 

인덱스 별 변하는 위치에 따라 규칙을 찾아서 구현해줄 수도 있지만, 시험 때는 시간이 부족할 수도 있으니 외워두는 것도 좋을 듯하다.

def rotate(x, y, l):
    
    # 회전한 배열 임시 저장 
    new =[ [0] * l for _ in range(l)]
    for i in range(l):
        for j in range(l):
            new[i][j] = graph[x+l-1-j][y+i]

    for i in range(l):
        for j in range(l):
            graph[x+i][y+j] = new[i][j]

두번째는 얼음의 양 줄일 때 !!!!!!!!!!

순차적으로 줄어들어야 할 얼음을 발견하면 바로 그 때 줄여주었는데, 그러면 이후 탐색 결과에 영향을 주었다.. 

따라서 줄어들어야할 얼음의 위치를 check라는 배열에 임시로 저장해두고 탐색이 끝난 후 얼음의 크기를 줄여주어야 했다.. 

 

전체적인 코드 구현은 조건에 따라 하나씩 따라가면 된다. 

 

아래 과정을 q 만큼 반복 

1. 나눠진 부분들에 대해 시계 방향 90도 회전

2. 줄어들어야 할 얼음 위치 저장 

3. 얼음 크기 줄이기 

 

남은 얼음의 양은 반복문으로 구하면 되고, 최대 얼음 크기는 bfs 알고리즘으로 구해주면 된다. 

from collections import deque 

# 얼음 크기 구하기 
def bfs(x,y):
    q= deque()
    
    q.append((x,y))
    # 얼음 크기 
    cnt = 1
    visited[x][y] = True
    while q :
        x, y = q.popleft() 
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0<=nx<2**n and 0<=ny<2**n and not visited[nx][ny] and graph[nx][ny]:
                visited[nx][ny] = True 
                q.append((nx,ny))
                cnt += 1  
                
    return cnt 
                
# 90도 회전 함수              
def rotate(x, y, l):
    
    new =[ [0] * l for _ in range(l)]
    for i in range(l):
        for j in range(l):
            new[i][j] = graph[x+l-1-j][y+i]

    for i in range(l):
        for j in range(l):
            graph[x+i][y+j] = new[i][j]
            
dx = [1,-1,0,0 ]
dy = [0,0,1,-1]

def solve(num):
    x = 0
    # 모든 격자 부분 시계 방향으로 90도 회전 
    while x < 2**n:
        
        for i in range(2**n//2**num):
            rotate(x, 2**num * i, 2**num)
        x += 2**num
	
    # 줄어들어야 할 얼음 위치 임시 저장 
    check = []
    # 줄어들어야 할 얼음 찾기 
    for i in range(2**n):
        for j in range(2**n):
            if graph[i][j] > 0 :
                cnt = 0
                for k in range(4):
                    nx = i + dx[k]
                    ny = j + dy[k]
                    
                    if 0<= nx <2**n and 0 <= ny < 2**n and graph[nx][ny]:
                        cnt += 1 
               
                if cnt < 3 :
                    check.append((i,j))
	# 얼음 크기 줄이기 
    for i, j in check:
        graph[i][j] -= 1 
                            
n, q = map(int,input().split())

graph = []

for _ in range(2**n):
    graph.append(list(map(int,input().split())))

L = list(map(int,input().split()))

for i in range(q):
    solve(L[i])

total = 0
# 남은 얼음의 양 
for i in range(2**n):
    for j in range(2**n):
        total += graph[i][j]
        
print(total)

visited = [ [False] * 2**n for _ in range(2**n)]

ans = 0
# 최대 얼음 크기 찾기 
for i in range(2**n):
    for j in range(2**n):
        if graph[i][j] and not visited[i][j]:
            ans = max(ans, bfs(i,j))
print(ans)