[코드트리] 파이썬 - 나무박멸

코드트리 - 나무박멸

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

# 소요시간 : 100분

# 접근 방법

• 구현, 시뮬레이션 문제로서 의사 코드를 탄탄히 작성하는데 집중하였다.
• 우선 주어진 조건을 정리하며 아래 키 포인트를 위주로 고민하였다.
  • 나무들이 동시에 움직이며, 나무가 성장한 후 번식을 한다는 점
  • 제초제는 가장 많은 나무가 박멸되는 위치에 뿌리고, 빈 칸을 만나는 경우에도 제초제를 뿌리고 종료하는 것
  • 제초제는 c년만큼 남아있고, 다시 뿌리면 c년으로 초기화된다는 점이다.
• 제초제를 따로 리스트에 보관하지 않고 주어진 arr에 기록하기 위하여 입력받은 후 벽을 -11로 변경하였다.
• 이후 제초제를 뿌린다면 -1 ~ -10까지로 나타내준다.
• 이후 M년만큼 진행해준다.
• 바로 grow 함수 실행
  • 새로 자라는 나무를 기록할 new_arr을 생성해준다.
  • 주어진 배열을 순회하며 나무가 있는 경우
  • 4방향을 탐색해준다.
    • 이 때, 나무의 성장을 위해 주변에 나무가 있는지 확인 할 cnt
    • 새로 자랄 공간을 확인할 new_grow, temp를 선언해주고
    • 빈 공간인 경우 위치를 temp에 기록, new_grow += 1
    • 나무인 경우 cnt += 1을 해준다.
  • 4방향 탐색이 끝난 후, 현재 나무의 위치는 cnt만큼 더해주고, temp가 있다면 val = 현재 위치의 나무 그루 // 새로 자랄 위치의 수를 new_arr에 계속 더해준다.
  • 모든 탐색이 끝난 후 new_arr에 값이 있다면, arr로 복사해준다.
• grow함수가 끝난 후 배열을 탐색하며 나무가 있는 경우 check_remove 함수를 실행해준다.
  • cnt의 초기 값은 현재 위치의 나무 그루
  • dr, dc는 대각선 방향 4개로 정의 해준 후 대각선 4방향을 범위 k만큼만 탐색해준다.
  • 범위 내이고, 나무라면 cnt에 더해주고, 아니라면 현재 방향 탐색을 종료해준다.
  • cnt를 리턴해준다.
• 현재 위치에서 제거할 수 있는 나무의 수가 val 보다 크다면, 현재 위치를 기록해주고 제거할 수 있는 나무의 수를 저장해준다.
• 모든 위치에서의 탐색이 끝난 후 기록해둔 위치에서 remove함수를 실행해준다.
• check_remove와 마찬가지로 탐색해주는데 제초제를 뿌리기 전, 기존의 제초제들을 +1 씩 해준다.
  • 제초제가 있는 칸 또는 나무가 있는 칸이면 -C로 제초제가 뿌려졌음을 표시해준다.

처음엔 범위 k를 생각해주지 않아서 시간을 잡아먹고, 나중에는 초기에 주어지는 나무의 최대 그루수 100을 착각하여 나무가 있는 칸을 확인할 때 <=100이라는 조건을 넣어줘서 문제를 해결하지 못하였다.

역시.. 의사코드 잘 짜고 조건을 꼼꼼히 확인하자..!!

import sys  
sys.stdin = open('input.txt')  
def grow():  
    new_arr = [[0] * N for _ in range(N)]  
    for i in range(N):  
        for j in range(N):  
            if 0 < arr[i][j]:  
                new_grow, cnt, temp = 0, 0, []  
                for d in range(4):  
                    ni, nj = i + di[d], j + dj[d]  
                    if 0 <= ni < N and 0 <= nj < N:  
                        if arr[ni][nj] == 0:  
                            new_grow += 1  
                            temp.append((ni, nj))  
                        elif 0 < arr[ni][nj]:  
                            cnt += 1  
                arr[i][j] += cnt  
                if temp:  
                    val = arr[i][j] // new_grow  
                    for ti, tj in temp:  
                        new_arr[ti][tj] += val  
    for i in range(N):  
        for j in range(N):  
            if new_arr[i][j]:  
                arr[i][j] = new_arr[i][j]  

def check_remove(ri, rj):  
    global K, C  
    cnt = arr[ri][rj]  
    dr, dc = [-1, 1, 1, -1], [-1, -1, 1, 1]  
    for d in range(4):  
        for k in range(1, K+1):  
            ni, nj = ri + dr[d]*k, rj + dc[d]*k  
            if 0 <= ni < N and 0 <= nj < N:  
                if arr[ni][nj] <= 0:  
                    break  
                else:  
                    cnt += arr[ni][nj]  
    return cnt  


def remove(r):  
    global C, K  
    ri, rj = r  
    dr, dc = [-1, 1, 1, -1], [-1, -1, 1, 1]  
    for i in range(N):  
        for j in range(N):  
            if -11 < arr[i][j] < 0:  
                arr[i][j] += 1  
    for d in range(4):  
        for k in range(1, K + 1):  
            ni, nj = ri + dr[d] * k, rj + dc[d] * k  
            if 0 <= ni < N and 0 <= nj < N:  
                if arr[ni][nj] <= 0:  
                    if arr[ni][nj] > -11:  
                        arr[ni][nj] = -C  
                    break  
                else:  
                    arr[ni][nj] = -C  
    arr[ri][rj] = -C  



N, M, K, C = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(N)]  

# 제초제 기록위해 벽 -11로 변경  
for i in range(N):  
    for j in range(N):  
        if arr[i][j] == -1:  
            arr[i][j] = -11  
di, dj = [1, 0, -1, 0], [0, -1, 0, 1]  
result = 0  
for _ in range(M):  
    grow()  
    val = 0  
    rem = [-1, -1]  
    for i in range(N):  
        for j in range(N):  
            if 0 < arr[i][j]:  
                tree_cnt = check_remove(i, j)  
                if tree_cnt > val:  
                    val = tree_cnt  
                    rem = [i, j]  
    result += val  
    remove(rem)  
    print(arr)  
print(result)