[백준 21610번] 마법사 상어와 바비라기 - python

문제 링크

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

21610번: 마법사 상어와 비바라기

 

풀이 

난이도가 그렇게 높지 않은 구현 문제이다. 

조건에 맞게 구현만 하면 되는 문제인데 디버깅에 적지 않은 시간이 걸렸다. 

문제 조건이 모든 구름이 이동이 끝난 후에 다음 단계로 넘어가야 하는데,

하나의 구름이 이동할 때마다 대각선을 탐색하여 물을 올려줬기 때문이었다. 

정말 사소한 실행 위치 차이가 .. ㅠㅠ 앞으로 이런 점에 유의해야겠다. 

# https://www.acmicpc.net/problem/21610

n, m = map(int,input().split())

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

graph = []

# 물의 양 
for _ in range(n):
    graph.append(list(map(int,input().split())))
    
move= []

# 현재 구름 위치 
cloud = [ (n-1,0), (n-1,1), (n-2, 0), (n-2,1) ]

# 구름 이동 방향과 속도 
for _ in range(m):
    move.append(list(map(int,input().split())))
   
# 대각선에 물 바구니 칸 수만큼 물의 양 올려주는 함수 
def cross(x,y):
    tmp_dx = [1, 1, -1, -1]
    tmp_dy = [-1, 1, -1, 1]
    
    for i in range(4):
        nx = x + tmp_dx[i]
        ny = y + tmp_dy[i]
        
        if 0<=nx <n and 0<=ny <n :
            if graph[nx][ny] > 0 :
                graph[x][y] += 1 
            
for i in range(m):
    d, s = move[i]
    d -= 1 
    # 5번 조건 체크용 
    tmp_set = set()
    # 새로 생긴 구름 
    new_cloud = []
    
    # 모든 구름 이동 
    for j in range(len(cloud)) :
        nx = (cloud[j][0] + dx[d] * s)% n
        ny = (cloud[j][1] + dy[d] * s)% n
        
        graph[nx][ny] +=1 
        new_cloud.append((nx,ny))
        tmp_set.add((nx,ny))
        
    # 이동 후 대각선 불 바구니 수에 따른 물의 양 올려주기 
    for nx, ny in new_cloud:
        cross(nx,ny)
        
    new = []
    
    # 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양 줄어듬 
    for a in range(n):
        for b in range(n):
            if graph[a][b] >= 2 and (a,b) not in tmp_set:
                new.append((a,b))
                graph[a][b] -= 2 
             
    # 구름은 모두 사라지므로, 새롭게 갱신 
    cloud = new 
    
ans = 0
for i in range(n):
    ans += sum(graph[i])
        
print(ans)