2주차 | 문제 4. 폭탄 구현하기
문제
아래와 같은 그림의 정사각형이 있다. 그림과 같이 정사각형을 동일한 크기의 칸으로 나누었다고 했을 때, 맨 오른쪽, 아래의 칸을 arr[n][n]이라고 표현한다. 모든 위치에는 폭탄 값이 있는데, 모든 폭탄 값의 초기 값은 0이다.
위 그림을 기준으로 나누어진 사각형 중 하나를 선택하여 폭탄을 떨어트립니다. 폭탄이 떨어진 지점은 arr[2][3]이라고 하면 아래의 노란색 모양으로 폭탄이 터진다.
위의 십자가 모양처럼 폭탄이 터지면 폭탄이 터져 영향을 받은 위치의 폭탄 값이 올라갑니다. 이를 그림으로 표현하면 아래와 같습니다. 이때 폭탄 값은 영향을 받는 횟수만큼 무한히 올라간다. 즉 같은 위치에 여러 번 영향을 받는다면, 그 만큼 폭탄 값이 증가한다.
폭탄이 터지는 위치들이 모두 주어졌을 때, 폭탄 값 규칙을 고려하여 모든 폭탄이 떨어졌을 때, 폭탄 값들의 합을 출력하시오.
입력
첫째 줄에 정사각형의 한 변의 길이 n(1≤n≤20)와 떨어트릴 폭탄의 개수 k(1≤k≤500,000)가 주어진다.둘째 줄부터 k줄에 걸쳐서 폭탄이 떨어질 위치가 주어진다.
a b값이 공백을 두고 주어지며, arr[a][b]위치에 폭탄이 떨어졌다는 것을 의미한다.
출력
모든 폭탄이 떨어졌을 때, 정사각형 내의 모든 폭탄 값을 합한 값을 출력하시오.
풀이
import numpy as np
n,k=map(int, input().split()) # 정사각형 한 변의 길이, 폭탄의 개수
list1=[[0]*(n+2)]*(n+2) # 그림과 같이 첫번째 칸을 [1][1], 마지막칸을 [n][n]으로 사용하기 위해 위아래, 좌우를 각각 +1씩한 (n+2)*(n+2)의 2차원 배열을 만들어줌
arr=np.array(list1)
for _ in range(k):
a,b=map(int,input().split()) # 폭탄이 떨어질 위치
# 폭탄에 영향을 받는 상하좌우에 +1
arr[a][b]+=1
arr[a][b+1]+=1
arr[a][b-1]+=1
arr[a+1][b]+=1
arr[a-1][b]+=1
bomb=arr[1:(n+1),1:(n+1)] # [1][1]부터 [n][n]까지만 잘라내기
print(np.sum(bomb))2차원 배열의 구현 및 연산을 위해 numpy를 사용하였다. 구름 알고리즘에서는 [0] 인덱스를 1번째로 항상 표현하는 것 같아 스스로 혼동하지 않기 위해서 n*n의 2차원 배열을 (n+2)*(n+2) 배열로 구현하여 테두리에 존재하는 영역은 신경쓰지 않기로 했다.
예를 들면, 문제에서 주어진 3*3 배열은 5*5로 생성하여 가운데 존재하는 3*3 영역만 생각하는 것이다. 이렇게 하면 위의 첫 번째 그림과 같이 첫번째 칸을 [1][1]로, 마지막 칸을 [3][3]으로 사용할 수 있게 된다.
5*5 크기의 배열 arr을 생성한 후, arr[a][b]에 폭탄이 떨어졌을 경우 폭탄에 의해 영향 받는 위치를 생각해보면 다음과 같다.
- arr[a][b]
- arr[a][b+1]
- arr[a][b-1]
- arr[a+1][b]
- arr[a-1][b]
위 5개의 위치에 +1씩 해주면 폭탄 값을 구할 수 있으며, 이 과정을 폭탄의 개수(k)만큼 반복한 후 3*3 크기로 배열을 잘라내기 위해 슬라이싱을 진행해준다.
잘라낸 배열 bomb의 모든 폭탄 값을 더하기 위해 np.sum을 사용한다.
구름 정답 코드에서는 데크를 이용하였는데, numpy를 이용하여 코드를 훨씬 간결하게 작성할 수 있었다.