[코드트리] [시뮬레이션] 십자 모양의 지속적 폭발

https://www.codetree.ai/missions/2/problems/cross-shape-continuous-bomb/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 

1이상 100이하의 숫자로 구성된 n * n 크기의 격자판이 주어집니다. 이때 특정 열을 선택하면, 해당 열에 숫자가 적혀있는 위치 중 가장 위에 있는 칸을 중심으로 십자 모양으로 폭탄이 터지게 됩니다. 십자 모양의 크기는 선택된 칸에 적혀있는 숫자로 정해지며, 터진 이후에는 중력에 의해 숫자들이 아래로 떨어지게 됩니다.

십자 모양의 크기는 선택된 숫자에 비례하여 커집니다. 선택된 숫자가 1인 경우에는 자기 자신만 터지게 되고, 선택한 숫자가 2인 경우에는 자신을 포함하여 인접한 4개의 격자 역시 터지게 되며, 3인 경우에는 자신을 제외한 상하좌우 방향으로 각각 2개씩이 더 터지게 됩니다. 숫자가 4 이상인 경우에도 마찬가지의 규칙에 따라 해당 범위만큼 터지게 됩니다.

 

 

예를 들어 다음 격자판에서 2번째 열을 선택하게 되면, 폭탄이 터지고 중력이 작용한 이후의 결과가 다음과 같이 나타나게 됩니다.

그 이후에 연달아 2번째 열을 다시 선택하게 되면, 다음과 같은 결과를 얻게 됩니다.

만약 또다시 2번째 열을 선택하게 되면, 다음과 같이 폭탄이 터져야 하는 범위가 격자 판을 벗어나게 되지만, 이 경우에는 격자 안에서만 폭탄이 터지게 됩니다.

이때 또 2번째 열을 선택하게 되면 두 번째 열에서는 더이상 터질 폭탄이 없습니다. 이러한 경우에는 아무 변화가 일어나지 않습니다.

초기 격자판의 상태와 폭탄이 터질 곳의 열의 위치가 순서대로 주어졌을 때, 순서대로 폭탄을 터뜨리고 중력이 작용하는 것을 반복한 이후의 결과를 출력하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에는 격자의 크기를 나타내는 n과 폭탄을 터뜨릴 횟수 m이 공백을 사이에 두고 주어집니다.

두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다.

그 다음 줄 부터는 m개의 줄에 걸쳐 폭탄을 터뜨릴 열의 위치 c가 순서대로 주어집니다. (1 ≤ c ≤ n)

• 1 ≤ n ≤ 200
• 1 ≤ m ≤ 10

출력 형식

m번에 걸쳐 폭탄이 터지고 중력이 작용한 것을 반복한 이후의 결과를 출력합니다.

n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자를 공백을 사이에 두고 출력합니다. 만약 해당 위치에 아무 숫자도 적혀있지 않은 경우라면 0을 출력합니다.

 

입출력 예제

예제1

입력:

4 4
1 1 2 3
3 2 2 3
3 1 6 2
4 5 4 4
2
2
2
2

 

출력: 

0 0 0 0
0 0 0 3
1 0 2 3
3 0 6 2

 

---

역시 가볍게 풀었다. 삼전 코테와 코드트리 시뮬레이션 부분을 최근 계속 풀어와서 그런가 한번에 잘 풀었다.

그냥 문제 그대로 구현하기만 하는 거로 딱히 머리 싸멜 필요없다.

 

import sys

dxs = [-1,1,0,0]
dys = [0,0,1,-1]

def in_range(nx,ny):
    return 0<=nx<n and 0<=ny<n

def gravity(x,y):
    for row in range(x,0,-1):
        board[row][y] = board[row-1][y]
        board[row-1][y] = 0
    

def explosion(x,y,power):
    board[x][y]=0
    if power==1:
        return
    for d in range(4):
        for p in range(1,power):
            nx = x+dxs[d]*p
            ny = y+dys[d]*p
            if in_range(nx,ny) and board[nx][ny]!=0:
                board[nx][ny]=0
                if d == 2 or d == 3:
                    gravity(nx,ny)

def print_board(board):
    for b in board:
        print(*b)
    print()

if __name__=="__main__":
    n,m = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(n)]
    
    for _ in range(m):
        col=int(input())
        col-=1
        for i in range(n):
            if board[i][col] != 0:
                power = board[i][col]
                explosion(i,col,power)
                break
                
    print_board(board)