[Python] 코드트리 - 나무 타이쿤

 

 

 

 

https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 3줄 요약

1. n x n 격자 모든 칸에 '리브로수' 라는 나무를 키우려고 한다.

2. 영양제를 맞으면 나무의 높이가 1씩 자라난다.

3. 영양제의 위치가 정해진 이동 규칙과 생성을 통해 이루어질 때, m년 이후의 리브로수 높이의 총합은?

 

---

 

역시 삼성기출문제 답게

문제만봐도 어질어질 ㅋㅎ

 

하지만!!

구현 문제인 만큼

차근 차근 읽고 하나 하나 작성하면 풀 수 있다.

 

 

3줄 요약에 담을 수 없는 세세한 조건들이 참 많았는데,

필자는 성장 순서대로 구현하려고 했습니다.

 

	## 1. 영양제 맞을 땅으로 이동
	for i in range(len(special)):
        special[i][0], special[i][1] = special[i][0]+(dx*d_cnt), special[i][1]+(dy*d_cnt)
        for j in range(2):
            if special[i][j] < 0: special[i][j] += n
            if special[i][j] >= n : special[i][j] = special[i][j]%n
        
        ## 2. 영양제 맞은 땅은 쑥쑥 자라라
        trees[special[i][0]][special[i][1]] += 1

 

여기서 dx와 dy는 이동 규칙 번호에 해당되는 좌표

문제에 주어진 이동 규칙은 아래 이미지와 같습니다.

 

 

주어진 번호에 따라 반시계 방향 이동 중

어떤 방향으로 이동할 지 정해진다.

---

중요한 건

초기 특수영양제 좌표인

좌측 하단 4칸에서 (이동 방향 * 이동 칸수) 를 더한 후

범위 밖으로 나간 좌표를 다시 반대로 돌아오게 하는 것..!

 

음수로 나간 경우에는 격자판 크기 만큼 더해주고,

n을 넘어선 경우에는 나머지를 구해서 좌표를 재설정 해준다.

 

---

 

처음엔

이동 칸수에 따라서 두 바퀴 이상 넘어갈 걸 고려해서

이동 횟수만큼 반복문을 돌려주려 하였다.

 

하지만 문제에 주어진 조건

 

즉,

n을 넘어서 이동하는 경우는 없으니 최대 1바퀴만 이동할 수 있다.

따라서 위와 같이 코드를 작성할 수 있었다.

 

 

다음은!

    ## 3. 영양제 맞은 땅의 대각선 체크
    for i in range(len(special)):
        for tx, ty in [[-1,-1], [-1,1], [1,-1], [1,1]]:
            x, y = special[i][0]+tx, special[i][1]+ty

            if 0<=x<n and 0<=y<n and trees[x][y]: 
                trees[special[i][0]][special[i][1]] += 1
    
    ## 4. 많이 자란 리브로수는 영양제로 만들기
    cut_trees = []
    for i in range(n):
        for j in range(n):
            if trees[i][j] >= 2 and ([i, j] not in special):
                trees[i][j] -= 2
                cut_trees.append([i,j])
    return cut_trees

 

앞서 했던 영양제 맞은 땅에서

대각선 네 가지 방향에 리브로수의 높이가 1이상인 갯수만큼 더 성장합니다.

 

나무들을 모두 성장시킨 후,

격자판에 크기가 2이상인 나무들은 베어서 영양제를 삽니다.

 

그리고

그 나무 위치에 영양제를 올려두는데요!!

참고로 기존에 영양제를 맞은 나무는 제외입니다.

 

그래서

잘린 나무들의 위치가 곧 영양제의 위치겠죠?

반환해서 영양제 리스트를 초기화 해줬습니다.

 

종합해보면,

def solve(trees, n, d, d_cnt, special):
    dx, dy = d

    ## 1. 영양제 맞을 땅으로 이동
    for i in range(len(special)):
        special[i][0], special[i][1] = special[i][0]+(dx*d_cnt), special[i][1]+(dy*d_cnt)
        for j in range(2):
            if special[i][j] < 0: special[i][j] += n
            if special[i][j] >= n : special[i][j] = special[i][j]%n
        
        ## 2. 영양제 맞은 땅은 쑥쑥 자라라
        trees[special[i][0]][special[i][1]] += 1

    ## 3. 영양제 맞은 땅의 대각선 체크
    for i in range(len(special)):
        for tx, ty in [[-1,-1], [-1,1], [1,-1], [1,1]]:
            x, y = special[i][0]+tx, special[i][1]+ty

            if 0<=x<n and 0<=y<n and trees[x][y]: 
                trees[special[i][0]][special[i][1]] += 1
    
    ## 4. 많이 자란 리브로수는 영양제로 만들기
    cut_trees = []
    for i in range(n):
        for j in range(n):
            if trees[i][j] >= 2 and ([i, j] not in special):
                trees[i][j] -= 2
                cut_trees.append([i,j])
    return cut_trees

n, m = map(int, input().split())
trees = [list(map(int, input().split())) for _ in range(n)]
move = [list(map(int, input().split())) for _ in range(m)]

direction = [(0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1)]
special = [[n-2,0], [n-2,1], [n-1,0], [n-1,1]]

for d, d_cnt in move:
    special = solve(trees, n, direction[d-1], d_cnt, special)

print(sum([sum(t) for t in trees]))

 

문제만 차근 차근 읽고

조건들을 잘 이해했다면 어렵지 않았을 거라 생각합니다!

 

끝!