[CodeTree] 십자 모양 폭발 (중력)

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

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

 

알고리즘

• 시뮬레이션

특정한 알고리즘을 요구하는 문제는 아니고 단순 시뮬레이션, 구현 문제이다.

문제 해결 과정

이 문제는 폭탄을 터뜨린 다음 중력이 작용했을 때 숫자들의 상태를 출력하는 문제이다.

 

먼저 폭탄이 터져서 숫자들이 사라졌다는 것을 0으로 표현한다.

 

숫자는 무조건 1이상 100이하이기 때문에 0이라면 숫자들이 터졌다는 것을 의미한다.

 

폭탄이 터질 때는 동서남북으로 터지기 때문에 dx, dy를 사용할 수 있다.

 

숫자에 따라 동서남북으로 터지는 길이가 늘어난다는 점을 고려해서 폭탄을 터뜨리는 코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
r, c = map(lambda x:int(x)-1, input().split())

# 동서남북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def can_go(x, y):
    return 0<=x<n and 0<=y<n

iteration = arr[r][c]
# 기존 배열의 터진 부분을 모두 0으로 만든다.
arr[r][c] = 0
for i in range(4):
    nx, ny = r+dx[i], c+dy[i]
    for _ in range(iteration - 1):
        if can_go(nx, ny):
            arr[nx][ny] = 0
            nx, ny = nx+dx[i], ny+dy[i]

 

중력이 작용할 때를 살펴보자.

 

폭탄이 터지고 난 뒤 아래와 같은 상황이라고 가정하자.

 

 

위 상황에서 중력을 적용하는 방법에는 여러가지 방법이 있지만 새로운 배열을 생성하는 편이 좋다.

 

이제 아래에서부터 순회하면서 0이 아닌 경우에만 배열에 값을 넣어주면 된다.

 

이를 위해서 새로운 배열의 인덱스 값을 저장해두고 0이 아닌 경우에만 계속 갱신해야 한다.

 

new_arr = [[0]*n for _ in range(n)]
for i in range(n):
    idx = n-1
    for j in range(n-1, -1, -1):
        # 0이 아닐 때만 추가
        if arr[j][i] != 0: 
            new_arr[idx][i] = arr[j][i]
            idx-=1
for row in new_arr:
    for col in row:
        print(col, end=' ')
    print()

 

최종 코드

import sys
input = sys.stdin.readline
n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
r, c = map(lambda x:int(x)-1, input().split())

# 동서남북
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def can_go(x, y):
    return 0<=x<n and 0<=y<n

iteration = arr[r][c]
# 기존 배열의 터진 부분을 모두 0으로 만든다.
arr[r][c] = 0
for i in range(4):
    nx, ny = r+dx[i], c+dy[i]
    for _ in range(iteration - 1):
        if can_go(nx, ny):
            arr[nx][ny] = 0
            nx, ny = nx+dx[i], ny+dy[i]

new_arr = [[0]*n for _ in range(n)]
for i in range(n):
    idx = n-1
    for j in range(n-1, -1, -1):
        # 0이 아닐 때만 추가
        if arr[j][i] != 0: 
            new_arr[idx][i] = arr[j][i]
            idx-=1
for row in new_arr:
    for col in row:
        print(col, end=' ')
    print()