Python3
문제
코드트리 나무타이쿤
키워드
- 시뮬레이션
- dx, dy
문제 풀이
문제 요구사항
n x n 격자의 칸에 리브로수의 각자 다른 높이와 각 년도의 이동 규칙이 주어질 때, 해당 년수가 모두 지나고 난 뒤 남아있는 리브로수 높이들의 총 합을 구하는 프로그램
n x n 격자에 서로 다른 높이를 가진 리브로수가 주어진다.
특수 영양제는 1 x 1 땅에 있는 리브로수의 높이를 1 증가시키며, 만약 해당 땅에 씨앗만 있는 경우에는 높이 1의 리브로수를 만들어낸다.
초기 특수 영양제는 n x n 격자의 좌하단의 4개의 칸에 주어진다.
⇒ [n-2][0], [n-2][1], [n-1][0], [n-1][1]
특수 영양제 이동 방향의 경우 1번부터 8번까지 → ↗ ↑ ↖ ← ↙ ↓ ↘으로 주어지며 이동 칸 수만큼 특수 영양제가 이동하게 된다.
⇒ dx = [0, 0, -1, -1, -1, 0, 1, 1, 1], dy = [0, 1, 1, 0, -1, -1, -1, 0, 1]
격자 바깥으로 나가면 반대편으로 돌아온다.
리브로수는 성장 규칙
- 특수 영양제를 이동 규칙에 따라 이동시킨다.
- 특수 영양제를 이동 시킨 후 해당 땅에 특수 영양제를 투입한다.
- 특수 영양제를 투입한 리브로수의 대각선으로 인접한 방향에 높이가 1 이상인 리브로수가 있는 만큼 높이가 더 성장한다. 대각선으로 인접한 방향이 격자를 벗어나는 경우에는 세지 않는다.
- 특수 영양제를 투입한 리브로수를 제외하고 높이가 2 이상인 리브로수는 높이 2를 베어서 잘라낸 리브로수로 특수 영양제를 사고, 해당 위치에 특수 영양제를 올려둔다.
다음 년도로 넘어가면 위의 4단계를 다시 반복한다.
변수 및 함수 설명
- N: 격자의 크기 n (3 ≤ n ≤ 15)
- M: 리브로수를 키우는 총 년 수 (1 ≤ m ≤ 100)
- tree: 서로 다른 리브로수의 높이 리스트 (0 ≤ 초기에 주어지는 리브로수의 높이 ≤ 100)
- d: 이동 방향 (1번부터 8번까지 각각 → ↗ ↑ ↖ ← ↙ ↓ ↘) (1 ≤ d ≤ 8)
- p: 이동 칸 수 (1 ≤ p ≤ min(n, 10))
- nutri: 영양제 리스트
풀이
(입력 및 선언)
- 격자의 크기와 총 년 수를 입력받는다
- 리브로수 높이를 입력받고 tree에 저장시킨다
- 총 년 수 만큼 이동 방향과 이동 칸 수를 입력받는다
- 조건에 의해 초기 영양제의 위치를 넣어준다
(총 M년까지 반복)
(영양제가 그리드 안에 위치하도록 만들기)
- 영양제 배열 크기만큼 반복한다
- 영양제를 이동시킨 곳이 0보다 작으면 +N한 값을 넣어준다
- 영양제를 이동시킨 곳이 N과 같거나 크면 %N한 값을 넣는다
(땅에 영양제 주기)
- nutri 배열을 돌면서 해당하는 tree에 +1만큼 해준다
(인접 대각선 찾기)
- nutri 배열을 돈다
- 대각선(dx, dy가 2, 4, 6, 8)만 반복한다
- 다음 이동할 위치를 nx, ny에 저장한다
- nx, ny가 0과 n사이에 있고(0 ≤ nx, ny < n), 높이가 1이상이면 cnt 값을 1 증가시킨다
- 대각선을 다 돌고 cnt 만큼을 arr(임시 배열) 안에 넣어 준다
(인접 대각선 높이 증가시키기)
- arr 배열을 돈다
- arr 배열 안에 있던 세로줄의 위치에 해당하는 tree에 cnt만큼 증가시킨다
(나무 자르기)
- 격자를 돌면서 tree 값이 2이상이고 영양제 배열 안에 없는 것들만 tree 높이를 -2 해준다
- 자른 나무들을 영양제 배열에 넣는다
(나무 높이 총합)
- 격자를 돌면서 총합을 출력한다
최종 코드
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, 1, 1, 0, -1, -1, -1, 0, 1]
N, M = map(int, input().split())
tree = []
nutri = [[N-2, 0], [N-2, 1], [N-1, 0], [N-1, 1]]
# 리브로수 높이 입력받기
for _ in range(N):
tree.append(list(map(int, input().split())))
# 영양제가 grid를 넘지 않게
def move_nutri(pos):
if pos < 0:
return pos + N
if pos >= N:
return pos % N
return pos
# 각 연도의 이동 규칙
for _ in range(M):
d, p = map(int, input().split())
# 영양제 이동
for i in range(len(nutri)):
nutri[i][0] = move_nutri(nutri[i][0] + dx[d] * p)
nutri[i][1] = move_nutri(nutri[i][1] + dy[d] * p)
# 땅에 영양제 주기
for n in nutri:
tree[n[0]][n[1]] += 1
# 인접 대각선 높이 증가시키기
arr = []
for i in range(len(nutri)):
cnt = 0
for d in [2, 4, 6, 8]:
nx = nutri[i][0] + dx[d]
ny = nutri[i][1] + dy[d]
if 0 <= nx < N and 0 <= ny < N:
# 높이가 1 이상이면 증가
if tree[nx][ny] > 0:
cnt += 1
arr.append([i, cnt])
for element in arr:
i = element[0]
cnt = element[1]
tree[nutri[i][0]][nutri[i][1]] += cnt
# 나무 자르기
for i in range(N):
for j in range(N):
if tree[i][j] >= 2 and ([i, j] not in nutri):
tree[i][j] -= 2
nutri.append([i, j])
# 높이 총 합
ans = 0
for i in tree:
for j in i:
ans += j
print(ans)
I mean