[구름톤 챌린지] 2주차 9일차 폭탄 구현하기 (2)

 

 

문제

---

$N \times N$ 크기의 정사각형 모양의 땅이 있다. 땅을 $1 \times 1$ 크기의 작은 땅으로 나누었을 때, 위에서 $y$번째, 왼쪽에서 $x$번째에 위치한 땅의 좌표를 $(y, x)$로 나타낸다. 추가로 모든 땅에는 폭탄 값이라고 하는 값이 있다. 모든 폭탄 값의 초기 값은 $0$이다.

$K$개의 폭탄을 이 땅 위에 떨어트리려고 한다. 어떤 $1 \times 1$ 크기의 땅 위에 폭탄을 떨어트리게 되면 폭탄이 떨어진 땅과, 그 땅에 상하좌우로 인접한 칸의 폭탄 값에 영향을 끼친다. 폭탄 값이 변하는 정도는 땅의 상태에 따라 다르다.

 

• $N \times N$ 크기의 영역 밖이거나, 땅의 상태가 # 이라면 폭탄 값은 변하지 않는다.
• 땅의 상태가 0 이라면 폭탄 값은 $1$ 증가한다.
• 땅의 상태가 @ 이라면 폭탄 값은 $2$ 증가한다.

모든 폭탄을 떨어트린 뒤에, 모든 땅의 폭탄 값 중에서 가장 높은 값을 출력해보자.

예제 설명

---

첫 번째 예제를 그림으로 표현하면 다음과 같다.

 

 

$(2, 2)$에 폭탄이 떨어지면 폭탄 값은 다음과 같이 변한다. 상태가 # 인 $(3, 2)$는 폭탄의 영향을 받지 않는다.

 

 

$(2, 3)$에 폭탄이 떨어지면 폭탄 값은 다음과 같이 변한다. 상태가 @ 인 $(1, 3)$은 폭탄 값이 2 증가한다.

 

 

마지막으로 $(1, 4)$에 폭탄이 두 개 떨어진 뒤의 폭탄 값은 다음과 같다.

 

모든 땅 중 가장 큰 폭탄 값은 6 이므로, 답으로 6을 출력해야 한다.

입력

---

첫째 줄에 땅의 한 변의 길이 $N$과 폭탄을 떨어트릴 횟수 $K$가 공백을 두고 주어진다.
다음 $N$개의 줄에는 땅의 상태를 나타내는 $N$개의 문자가 공백을 두고 주어진다. $r$번째 줄에서 $c$번째로 주어지는 문자는 $(r, c)$ 좌표에 해당하는 땅의 상태이다.
다음 $K$개의 줄에는 폭탄을 떨어트릴 땅의 좌표를 나타내는 $y, x$가 공백을 두고 주어진다. 이는 $(y, x)$ 좌표에 폭탄을 떨어트린다는 의미이다.

 

• $1 \leq N \leq 200$
• $1 \leq K \leq 500 \ 000$
• 땅의 상태는 0, @, # 중 하나이다.
• $1 \leq y,x \leq N$
• 입력에서 주어지는 모든 수는 정수이다.

출력

---

모든 폭탄을 떨어트린 뒤에, 모든 땅의 폭탄 값 중에서 가장 높은 값을 출력한다.

 

---

문제 접근 방식

---

단순한 구현 문제로, BFS를 구현 할 때처럼 $4$방향 탐색을 진행해주면 된다.

 

총 시간 복잡도는 $O(5K + N^2)$이다.

 

---

정답 코드

---

# 폭탄 구현하기 (2)
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
bomb = [input().rstrip().split() for _ in range(N)]
matrix = [[0 for _ in range(N)] for _ in range(N)]
dr = [-1, 0, 0, 1]
dc = [0, -1, 1, 0]
for _ in range(K):
    r, c = map(lambda x: int(x)-1, input().rstrip().split())
    if bomb[r][c] == '0':
        matrix[r][c] += 1
    elif bomb[r][c] == '@':
        matrix[r][c] += 2
    for i in range(4):
        nr, nc = r+dr[i], c+dc[i]
        if 0 <= nr < N and 0 <= nc < N:
            if bomb[nr][nc] == '0':
                matrix[nr][nc] += 1
            elif bomb[nr][nc] == '@':
                matrix[nr][nc] += 2
max_val = 0
for i in range(N):
    for j in range(N):
        if max_val < matrix[i][j]:
            max_val = matrix[i][j]
print(max_val)

 

---

특별히 배운 점

---

기존 문제와 색다른 점은 경우를 나눠서 더해줘야 한다는 점 하나 밖에 없어서 쉬웠던 것 같다.