나무 타이쿤

https://www.codetree.ai/training-field/frequent-problems/problems/tree-tycoon/description?page=2&pageSize=20 

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

 

1. 실패 leaf_graph 로 성장할 나무의 위치를 체크했는데 leaf_graph[y][x] 가 아니라 leaf_graph 자체를 True로 바꿔버리는 실수를 했다. 뭐 이런 실수를 다하는지 모르겠다. 진짜. 사소한 실수를 줄여야 하는데 쉽지가 않음. 바본가싶다.

#n , m
#그래프
#규칙 d, p 
import copy
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
rules = [list(map(int, input().split())) for _ in range(m)]
leaf_graph = [[False for _ in range(n)] for _ in range(n)]
grow_leaf = []
# 3 ≤ n ≤ 15
# 1 ≤ m ≤ 100
# 0 ≤ 초기에 주어지는 리브로수의 높이 ≤ 100
# 1 ≤ d ≤ 8
# 1 ≤ p ≤ min(n, 10)


# n*n 리브로수
# 특수 영양제 -> 리브로수 높이 1 증가 씨앗만 잇는 경우 -> 1
# 좌측하단 4개 칸
leaf_graph[n - 1][0], leaf_graph[n - 2][0], leaf_graph[n - 1][1], leaf_graph[n - 2][1] = True, True, True, True


# → ↗ ↑ ↖ ← ↙ ↓ ↘ 격자 밖 이동시 돌아옴.
dy , dx = [0,-1,-1,-1,0,1,1,1],[1,1,0,-1,-1,-1,0,1]

#리브로수 성장
def find_grow():
    locations = []
    global leaf_graph, n 
    for y in range(n):
        for x in range(n):
            if leaf_graph[y][x]:
                locations.append([y, x])
    return locations

def validation(ny, nx):
    global n
    return 0 <= ny < n and 0 <= nx < n

def leaf_check(y, x):
    global graph
    dy, dx = [-1, -1, 1, 1],[-1, 1, -1, 1]
    grow_count = 0
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if validation(ny, nx):
            if graph[ny][nx] >= 1:
                grow_count += 1
    return grow_count

def move_leaf(locations, d, p):
    global leaf_graph, dy, dx, n, graph, grow_leaf
    leaf_graph = [[False for _ in range(n)] for _ in range(n)] #그래프 초기화
    
    for y, x in locations: #1씩 먼저 성장
        ny = (y + (n * 4) + (dy[d] * p)) % n
        nx = (x + (n * 4) + (dx[d] * p)) % n
        grow_leaf.append([ny, nx])
        graph[ny][nx] += 1

    tmp_graph = copy.deepcopy(graph) #그래프 카피

    for y, x in locations: #방향 체크후 1이상인 나무 개수 만큼 더 증가
        ny = (y + (n * 4) + (dy[d] * p)) % n
        nx = (x + (n * 4) + (dx[d] * p)) % n
        tmp_graph[ny][nx] += leaf_check(ny, nx)
    graph = tmp_graph # 그래프 동기화


def leaf_grow(d, p): #방향, 거리
    locations = find_grow()
    #그래프 초기화해야 할듯 !
    moved_locations = move_leaf(locations,d ,p)
    #

def remove_leaf():
    global graph, n, grow_leaf
    for y in range(n):
        for x in range(n):
            if graph[y][x] >= 2 and [y,x] not in grow_leaf:
                graph[y][x] -= 2
                leaf_graph = True
    grow_leaf = []
def print_total_leaf():
    global graph, n
    total = 0
    for y in range(n):
        for x in range(n):
            total += graph[y][x]
    print(total)
    
for year in range(m):
    d, p = rules[year]
    leaf_grow(d - 1, p)
    remove_leaf()

print_total_leaf()

 

 

2. 성공 코드

#n , m
#그래프
#규칙 d, p 
import copy
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
rules = [list(map(int, input().split())) for _ in range(m)]
leaf_graph = [[False for _ in range(n)] for _ in range(n)]
grow_leaf = []
# 3 ≤ n ≤ 15
# 1 ≤ m ≤ 100
# 0 ≤ 초기에 주어지는 리브로수의 높이 ≤ 100
# 1 ≤ d ≤ 8
# 1 ≤ p ≤ min(n, 10)


# n*n 리브로수
# 특수 영양제 -> 리브로수 높이 1 증가 씨앗만 잇는 경우 -> 1
# 좌측하단 4개 칸
leaf_graph[n - 1][0], leaf_graph[n - 2][0], leaf_graph[n - 1][1], leaf_graph[n - 2][1] = True, True, True, True


# → ↗ ↑ ↖ ← ↙ ↓ ↘ 격자 밖 이동시 돌아옴.
dy , dx = [0,-1,-1,-1,0,1,1,1],[1,1,0,-1,-1,-1,0,1]

#리브로수 성장
def find_grow():
    locations = []
    global leaf_graph, n 
    for y in range(n):
        for x in range(n):
            if leaf_graph[y][x]:
                locations.append([y, x])
    return locations

def validation(ny, nx):
    global n
    return 0 <= ny < n and 0 <= nx < n

def leaf_check(y, x):
    global graph
    dy, dx = [-1, -1, 1, 1],[-1, 1, -1, 1]
    grow_count = 0
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if validation(ny, nx):
            if graph[ny][nx] >= 1:
                grow_count += 1
    return grow_count

def move_leaf(locations, d, p):
    global leaf_graph, dy, dx, n, graph, grow_leaf
    leaf_graph = [[False for _ in range(n)] for _ in range(n)] #그래프 초기화
    
    for y, x in locations: #1씩 먼저 성장
        ny = (y + (n * 4) + (dy[d] * p)) % n
        nx = (x + (n * 4) + (dx[d] * p)) % n
        grow_leaf.append([ny, nx])
        graph[ny][nx] += 1

    tmp_graph = copy.deepcopy(graph) #그래프 카피

    for y, x in locations: #방향 체크후 1이상인 나무 개수 만큼 더 증가
        ny = (y + (n * 4) + (dy[d] * p)) % n
        nx = (x + (n * 4) + (dx[d] * p)) % n
        tmp_graph[ny][nx] += leaf_check(ny, nx)
    graph = tmp_graph # 그래프 동기화


def leaf_grow(d, p): #방향, 거리
    locations = find_grow()
    #그래프 초기화해야 할듯 !
    moved_locations = move_leaf(locations,d ,p)
    #

def remove_leaf():
    global graph, n, grow_leaf
    for y in range(n):
        for x in range(n):
            if graph[y][x] >= 2 and [y,x] not in grow_leaf:
                graph[y][x] -= 2
                leaf_graph[y][x] = True
    grow_leaf = []
def print_total_leaf():
    global graph, n
    total = 0
    for y in range(n):
        for x in range(n):
            total += graph[y][x]
    print(total)
    
for year in range(m):
    d, p = rules[year]
    leaf_grow(d - 1, p)
    remove_leaf()
print_total_leaf()