[삼성SW역량][Python/BOJ] 백준 21610 마법사 상어와 비바라기(구현)

그저 빡구현!!

 

삼성 문제 풀다보니까 익숙해진다. 

 

 

 

문제  : 

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

 

 

 

 

 

이 문제는 내가 스스로 풀뻔 했으나  아쉽...

계속 시간초과가 났다. 

 

 

 

3에서 구름이 사라진 칸이 아니여야한다 부분이 문제였다. 

처음에 not in을 이용해서 3에서 구름이 사라진 진 칸과 비교하였다. 그래서 시간 초과가 발생하였다.

 

vis를 이용해서 m을 돌때마다 갱신하고 3에서 사라진 구름의 위치를 알아낼 수 있게 만들었더니 시간초과는 해결되었다. 

 

 

 

 

 

코드 : 

 

dx = [0,-1,-1,-1,0,1,1,1]
dy = [-1,-1,0,1,1,1,0,-1]
            
     
            
if __name__=="__main__" :
    diagonal = [1,3,5,7]
    n,m = map(int,input().split())
    water = [list(map(int,input().split())) for i in range(n)]
    # 방향을 입력받음 
    ds = [list(map(int,input().split())) for i in range(m)]
    
    # 구름의 첫 위치 
    cloud = [[n-1,0],[n-1,1],[n-2,0],[n-2,1]]
    
    for d,s in ds :
        vis = [[0]*n for i in range(n)]
        
        next_cloud = []
        for idx in range(len(cloud)) :
            x,y = cloud[idx]
            # d방향으로 s칸 이동 
            nx,ny = (x+dx[d-1]*s)%n, (y+dy[d-1]*s)%n
            # 물의 양 1 증가 
            water[nx][ny] +=1 
            # 이동한 구름의 위치 저장 
            vis[nx][ny] = 1 
            next_cloud.append([nx,ny])
    
        for x,y in next_cloud :
            # 대각선 방향으로 
            cnt = 0 
            for i in diagonal :
                nx,ny = x + dx[i], y + dy[i]
                if 0<=nx<n and 0<=ny<n and water[nx][ny] :
                    cnt+=1 
            water[x][y] += cnt 
        
        cloud = []
        for i in range(n) :
            for j in range(n) :
                # 바구니에 저장된 물의 양이 2 이상이고 구름이 사리진 칸이 아니여야한다. 
                if water[i][j] >=2 and vis[i][j] == 0:
                    water[i][j] -=2 
                    # 새로운 구름의 위치 
                    cloud.append([i,j])
        
    print(sum(sum(water,[])))