알고리즘/9oormthon Challenge
[구름톤 챌린지 #9] 폭탄 구현하기 (2)
young_and_mini
2023. 8. 24. 18:47
구름LEVEL
난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.
level.goorm.io
문제 해결 방법
2 차원 리스트를 두 개를 운용해야한다는 점만 고려하면, 완전탐색을 이용하여 간단하게 구현되는 문제이다.
input 값으로 주어지는 k 개의 (x,y) 좌표와 그 주변 영역에 대해서 고려할 사항은 아래와 같다. (문제에서는 (y,x) 좌표라고 언급되었지만, 편의 상 (x,y)로 사용하였다.)
- 위, 아래, 왼쪽, 오른쪽이 N * N 영역의 밖에 위치한 경우는 무시된다.
- 땅 상태가 "#"이라면, 그 땅은 영향받지 않는다.
- 땅 상태가 "0"이라면, 폭탄 값을 1 증가시켜야 한다.
- 땅 상태가 "@"라면 폭탄 값을 2 증가시켜야 한다.
우선 1번 조건은 폭탄 값 리스트의 크기를 한 칸 늘려주어서 해결하였다. 크기를 한 칸 늘리면 index가 -1 인 상황과 n 인 상황 모두 커버할 수 있게 되므로, 폭탄의 영향 범위를 매번 고려해주지 않아도 된다는 이점이 생긴다.
나머지 조건은 폭탄이 떨어졌을 때 영향이 미치는 범위들에 대해 각각, 땅 상태 리스트의 값이 "0"일 때는 해당 좌표의 폭탄 값을 1 증가시키고, "@"일 때는 폭탄 값을 2 증가시키면 된다.
위 내용을 코드로 구현하면 아래와 같다.
import sys
n, k = map(int, sys.stdin.readline().split())
#테두리 바깥은 신경쓰지 않아도 되도록
score_arr = [([0 for i in range(n)]+[-sys.maxsize]) for j in range(n)]
score_arr.append([-sys.maxsize for i in range(n+1)])
#테두리 바깥은 -1로 표시 ("0", "@"가 아니면 어떤 값도 상관 없다.)
ground_arr = [(list(sys.stdin.readline().split()) + ["-1"]) for j in range(n)]
ground_arr.append(["-1" for i in range(n+1)])
def be_affected(x,y):
global score_arr, ground_arr
if ground_arr[x][y] == "0":
score_arr[x][y] += 1
return
if ground_arr[x][y] == "@":
score_arr[x][y] += 2
return
#그 외의 경우에는 의미 없음
return
dx = [0, 0, 0, -1, 1]
dy = [0, -1, 1, 0, 0]
for _ in range(k):
bombing_x, bombing_y = map(int, sys.stdin.readline().split())
for i in range(5):
affected_x = bombing_x-1 + dx[i]
affected_y = bombing_y-1 + dy[i]
be_affected(affected_x, affected_y)
max_score = 0
for row in score_arr:
max_score = max(max_score, max(row))
print(max_score)