[코드트리][기출문제] 나무 박멸
자료구조를 제외한 라이브러리 최대한 사용하지 않고 문제풀기 (필요하면 직접 코딩)
문제
문제 풀이 및 회고
class 만들어서 풀어봤다. 1시간 쯤 걸린듯 금방 풀어도 한번에 푸는 꼼꼼함을 좀 잘 길러야할듯
코드(python)
from collections import defaultdict
# n*n 격자.
# 제초제의 경우 k 범위 대각선으로 퍼짐(벽있으면 막힘)
# 1. 나무 있는 칸에 나무들 +1
# 2. 나무들 인접한 4개의 칸 중에 빈 칸에는 번식 시작하는데 번식은 (해당 칸)//빈칸 수
# 3. 각 칸 중 제초제 뿌렸을 때 나무 가장 많이 박멸되는 칸에 제초제를 뿌림. 나무 있는 칸에 제초제 뿌리면 4개의 대각선으로 전파됨
# 단 도중에 벽이 있거나 아예 빈칸인 경우, 그 칸까지는 제초제가 뿌려짐. 그 이후 칸으로는 전파X
# 제초제가 뿌려진 칸에는 c년만큼 제초제가 남아있다가 c+1년째 될 때 사라짐
# 제초제 뿌려진 곳에 다시 뿌려지는 경우 새로 뿌려진 해로부터 다시 c년동앙 유지
# 박멸시키는 나무의 수가 동일한 칸이 있으면 행이 작은 순, 열이 작은 순
class Forest:
def __init__(self, size, k, c, board, DEAD_AREA):
self.size = size # n
self.k = k # k
self.c = c # c
self.board = board # board[y][x]
self.DEAD_AREA = DEAD_AREA # dict[(y, x)] = c
self.dy = [0,0,1,-1] # 상하좌우
self.dx = [1,-1,0,0]
self.diag = [(1,1), (1,-1), (-1,1), (-1,-1)] # 대각선 4 방향
def grow_tree(self):
"""
# 1. 나무 있는 칸에 나무들 +1
"""
for y in range(self.size):
for x in range(self.size):
if self.board[y][x] >= 1:
cnt = 0 # 주변 나무 있는 수만큼 grow
for i in range(4):
ny, nx = y + self.dy[i], x + self.dx[i]
if (0 <= ny < self.size and 0 <= nx < self.size) and self.board[ny][nx] > 0: # board 안이면서 나무가 있으면
cnt += 1
self.board[y][x] += cnt
return None
def spread_tree(self):
"""
# 2. 나무들 인접한 4개의 칸 중에 빈 칸에는 번식 시작하는데 번식은 (해당 칸)//빈칸 수
"""
dy, dx = [1,-1,0,0], [0,0,1,-1]
next_board = [line[:] for line in self.board]
for y in range(self.size):
for x in range(self.size):
if self.board[y][x] > 0: # 나무가 있다면 spread 준비
spread_area = [] # 퍼질 곳
for i in range(4):
ny, nx = y + self.dy[i], x + self.dx[i]
if (0 <= ny < self.size and 0 <= nx < self.size) and self.board[ny][nx] == 0: # board 안이면서 빈칸이면
if self.DEAD_AREA[(ny, nx)] == 0: # 제초제가 없다면
spread_area.append((ny, nx))
for ny, nx in spread_area: # 퍼뜨려야지 반드시 퍼뜨려야지
next_board[ny][nx] += self.board[y][x]//len(spread_area)
self.board = next_board
return None
def show_board(self, show="default"):
"""
board 보여주기
"""
print("******************", show, "******************",)
for i in range(self.size):
print(self.board[i])
return None
def find_maximum_target(self):
target = [0, self.size, self.size] # 가장 많이 죽이면서, 행이 작은 순, 열이 작은 순
for y in range(self.size):
for x in range(self.size):
if self.board[y][x] <= 0: # 벽이거나 빈칸이면 무시
continue
kill_num = 0
kill_num += self.board[y][x] # 해당 자리 나무 수
for dy, dx in self.diag: # 대각선 네 방향
for k in range(1, self.k+1):
ny, nx = y + k*dy, x + k*dx
if (0 <= ny < self.size and 0 <= nx < self.size) and self.board[ny][nx] > 0: # 내부면서 나무가 있음
kill_num += self.board[ny][nx]
else: # 밖이거나 벽이거나 빈칸이면 그만!
break
now_target = [kill_num, y, x]
if target[0] < now_target[0]: # 킬이 더 많음
target = now_target
elif target[0] == now_target[0]: # 킬이 같음
if target[1] > now_target[1]: # 행이 더 작음
target = now_target
elif target[1] == now_target[1]: # 행이 같음
if target[2] > now_target[2]: # 열이 더 작음
target = now_target
#target.append(now_target)
#target = sorted(target, key=lambda z:(-z[0], z[1], z[2])) # now_target과 target 중에 킬이 더 많고 행이 더 작고 열이 더 작은거로
return target
def kill_now(self, target):
# 제초제 하나씩 지우기
for k, v in self.DEAD_AREA.items():
if v != 0:
self.DEAD_AREA[k] -= 1
y, x = target[1], target[2]
self.board[y][x] = 0 # 나무 죽음 ㅠ
self.DEAD_AREA[(y, x)] = self.c # 제초제 뿌리기
# 대각선 네 방향
for dy, dx in self.diag:
for k in range(1, self.k+1):
ny, nx = y + k*dy, x + k*dx
if (0 <= ny < self.size and 0 <= nx < self.size) and self.board[ny][nx] > 0: # 내부면서 나무가 있음
self.board[ny][nx] = 0 # 나무 죽음 ㅠ
self.DEAD_AREA[(ny, nx)] = self.c # 제초제 뿌리기
elif (0 <= ny < self.size and 0 <= nx < self.size): # 내부인데 나무가 없거나 벽
self.DEAD_AREA[(ny, nx)] = self.c
break
else: # 외부
break
return None
def solution(n: int, m: int, k: int, c: int, board: list):
"""
m년동안 죽는 나무 구하기
"""
answer = 0
DEAD_AREA = defaultdict(lambda: 0) # 처음에 제초제 뿌려지면 c년 유지. 제초제가 뿌려지지 않은 곳은 그냥 0으로 빈칸을 찾기 위함
FOREST = Forest(n, k, c, board, DEAD_AREA) # Forest 초기화
#FOREST.show_board("start")
stop = -1
for year in range(1, m+1):
FOREST.grow_tree()
if year == stop:
FOREST.show_board("grow")
FOREST.spread_tree()
if year == stop:
FOREST.show_board("spread")
target = FOREST.find_maximum_target() # 제초제 뿌릴 곳 찾기
if target[0] == 0: # 이제 뿌릴 곳이 없음 나무가 다 죽었엉
break
FOREST.kill_now(target) # 제초제 뿌려잇!
#print(target)
if year == stop:
FOREST.show_board("kill")
#print(FOREST.DEAD_AREA)
answer += target[0] # 나무 죽인 수 더하기
if year == stop:
print(year, "year end")
break
return answer
if __name__ == "__main__":
# 변수 초기화
n, m, k, c = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
# 결과 출력
result = solution(n, m, k, c, board)
print(result)
댓글남기기