[코테준비] 삼성12. 코드트리: 나무박멸 python

백준보다는 코드트리에 더 신형 문제가 있는 것 같아서 코드트리로 넘어왔다!

코드트리- 삼성 SW 역량테스트 기출문제 링크: https://www.codetree.ai/training-field/frequent-problems

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

 

나무박멸 

• 링크: https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all/description
• 난이도:골드 4
• 분류: dx dy technique, simulation
• 직접 푼 여부: O
• 언어: 파이썬

풀이 노트

아래 1)2)3)4) 과정을 생각하며 어떻게 풀지 계획하였고, 그 뒤에 코드 구현을 하였다. 

빨간색 글씨는 처음에는 생각 못하고 풀어서 디버깅하며 다시 생각한 것이다.. 후 4번만에 맞았다. 언제쯤 한번에 맞을 수 있을까

주의 사항

1. 문제 잘보기!!!  조건들을 빼먹지는 않았는지 잘 체크 해야한다.

    (1) 주변에 나무가 있는 칸 수 만큼 성장

    (2) 제초제는 나무가 없는 곳까지 뿌려짐 (뿌려지기 시작했다면) 하지만, 벽에는 안 뿌려지고, 나무가 없는 곳이나 제초제가 뿌려져있는 곳을 지나고 나면 그 다음에는 안 뿌려진다. 

 

2. 번식을 할 때는 한번에 하므로, deepcopy로 복사한 후에 해야한다. 

3. 제초제를 뿌리면, treemap에서 나무를 없애야한다. 

 

정답 코드 💻

# 나무 박멸
import sys
import copy

input = sys.stdin.readline
# input------
n, m, k, c = map(int, input().split()) #n: 격자크기, m: 몇년실행, k: 몇칸까지 제초제, c:제초제 몇년 지속
treemap = [list(map(int, input().split())) for _ in range(n)]

herbicidemap = [[0]*n for _ in range(n)]


# 재료
# 제초제 를 위해
digonalr = [-1,-1,1,1]
digonalc = [-1,1,-1,1]
# 증식을 위해
dr =[-1,1,0,0]
dc = [0,0,-1,1]
# 1) grow ------
def grow():
    """
    나무자라나는 것 구현
    나무있는 곳 +1
    """
    global treemap
    for i in range(n):
        for j in range(n):
            if treemap[i][j]>0:
                cnt =0
                for direction in range(4):
                    newr, newc = i+dr[direction], j + dc[direction]
                    if 0<=newr<n and 0<=newc<n and treemap[newr][newc]>0:
                        cnt+=1
                treemap[i][j]+=cnt
    return treemap

# 2) multiplicate
def multiplicate():
    """
    나무 증식
    1) 빈칸으로 증식 (4방) -> treemap ==0 &  herbicidemap ==0
    2) 증식하는 수: 나무수 // 증식가능한 공간 수
    """
    global treemap, herbicidemap
    temptreemap = copy.deepcopy(treemap)
    for i in range(n):
        for j in range(n):
            if temptreemap[i][j]>0: # 나무가 있다면, 주변 탐색하며 증식
                cnt = 0
                points =[]
                for direction in range(4):
                    newr = i + dr[direction]
                    newc = j + dc[direction]
                    if 0<=newr<n and 0<=newc<n and temptreemap[newr][newc] ==0 and herbicidemap[newr][newc] ==0:
                        # 범위 안벗어나고, 빈칸 & 제초제 없으면
                        cnt+=1
                        points.append((newr, newc))
                if cnt>0:
                    multitree = temptreemap[i][j] // cnt
                    for p in points:
                        ii, jj = p
                        treemap[ii][jj] += multitree # 다른나무에서 번식한곳에 또 번식할 수 있으니


# 3) herbicide search
def herbicide_search():
    """
    제초제 뿌릴 곳 search
    1) 모든 점 이동
    2) 각 점에서 대각선 4군데로 이동하며 값& 위치 저장
    3) max값인 것 return: deadtreecout, 제초제 뿌려질 위치들 [(),()...] =? [int, (),()...]
    """
    global treemap
    maxcount =0
    points =[]
    for i in range(n):
        for j in range(n):
            temppoints = [] #각 점마다 초기화
            tempcount = 0
            if treemap[i][j]>0:
                # 나무가 있어야지만 시작
                tempcount+=treemap[i][j]
                temppoints.append((i,j))
                for diretion in range(4):
                    # 대각선 4방향
                    newr, newc = i, j
                    endflag = False
                    for kk in range(k): # k까지 이동 가능
                        newr, newc = newr+digonalr[diretion], newc+digonalc[diretion]
                        if 0<=newr<n and 0<=newc<n:
                            if treemap[newr][newc] >0 and not endflag:
                                tempcount +=treemap[newr][newc] # 죽인 나무 수 count
                                temppoints.append((newr,newc))# 간 위치 추가
                            elif treemap[newr][newc] ==0:
                                # 중간에 제초제나 빈칸이면 point는 append
                                endflag = True
                                temppoints.append((newr,newc))# 간 위치 추가
                                break
                            elif treemap[newr][newc] ==-1:
                                # 벽 만나면
                                break
                        else: break # 범위 넘어가는 순간 다른 방향으로
            if maxcount<tempcount: # 한 점에 대해 분석 끝내면, 비교해서 max update
                maxcount=tempcount
                points = temppoints

    return [maxcount, points]

# 4) herbicide ---------
def herbicide():
    """
    제초제 뿌리기
    1) 원래 있던 제초제 -1
    2) 제초제 뿌려질 위치 받아온 것 -> 값 세팅
    """
    global treemap, herbicidemap
    # 위치 받기
    current_deadtreecount, points =herbicide_search()
    # 전 제초제 -1
    for i in range(n):
        for j in range(n):
            if herbicidemap[i][j]>0:
                herbicidemap[i][j] -=1
    # 새 제초제 뿌리기 - 제초제 map, treep map
    for p in points:
        i, j = p
        herbicidemap[i][j] = c
        treemap[i][j] =0 # 나무 사라짐

    return current_deadtreecount
# main
deadtreecount =0
for i in range(m):
    # m년동안 박멸
    grow()
    multiplicate()
    current_deadtreecount= herbicide()
    deadtreecount+=current_deadtreecount

print(deadtreecount)

 

정답!

 

 

다시 생각해보니, 중간에 endflag를 쓸 필요가 없다는 것을 깨달았다.

더 간단한 코드이다. (아주 조금 더)

# 나무 박멸
import sys
import copy

input = sys.stdin.readline
# input------
n, m, k, c = map(int, input().split()) #n: 격자크기, m: 몇년실행, k: 몇칸까지 제초제, c:제초제 몇년 지속
treemap = [list(map(int, input().split())) for _ in range(n)]

herbicidemap = [[0]*n for _ in range(n)]


# 재료
# 제초제 를 위해
digonalr = [-1,-1,1,1]
digonalc = [-1,1,-1,1]
# 증식을 위해
dr =[-1,1,0,0]
dc = [0,0,-1,1]
# 1) grow ------
def grow():
    """
    나무자라나는 것 구현
    나무있는 곳 +1
    """
    global treemap
    for i in range(n):
        for j in range(n):
            if treemap[i][j]>0:
                cnt =0
                for direction in range(4):
                    newr, newc = i+dr[direction], j + dc[direction]
                    if 0<=newr<n and 0<=newc<n and treemap[newr][newc]>0:
                        cnt+=1
                treemap[i][j]+=cnt
    return treemap

# 2) multiplicate
def multiplicate():
    """
    나무 증식
    1) 빈칸으로 증식 (4방) -> treemap ==0 &  herbicidemap ==0
    2) 증식하는 수: 나무수 // 증식가능한 공간 수
    """
    global treemap, herbicidemap
    temptreemap = copy.deepcopy(treemap)
    for i in range(n):
        for j in range(n):
            if temptreemap[i][j]>0: # 나무가 있다면, 주변 탐색하며 증식
                cnt = 0
                points =[]
                for direction in range(4):
                    newr = i + dr[direction]
                    newc = j + dc[direction]
                    if 0<=newr<n and 0<=newc<n and temptreemap[newr][newc] ==0 and herbicidemap[newr][newc] ==0:
                        # 범위 안벗어나고, 빈칸 & 제초제 없으면
                        cnt+=1
                        points.append((newr, newc))
                if cnt>0:
                    multitree = temptreemap[i][j] // cnt
                    for p in points:
                        ii, jj = p
                        treemap[ii][jj] += multitree # 다른나무에서 번식한곳에 또 번식할 수 있으니


# 3) herbicide search
def herbicide_search():
    """
    제초제 뿌릴 곳 search
    1) 모든 점 이동
    2) 각 점에서 대각선 4군데로 이동하며 값& 위치 저장
    3) max값인 것 return: deadtreecout, 제초제 뿌려질 위치들 [(),()...] =? [int, (),()...]
    """
    global treemap
    maxcount =0
    points =[]
    for i in range(n):
        for j in range(n):
            temppoints = [] #각 점마다 초기화
            tempcount = 0
            if treemap[i][j]>0:
                # 나무가 있어야지만 시작
                tempcount+=treemap[i][j]
                temppoints.append((i,j))
                for diretion in range(4):
                    # 대각선 4방향
                    newr, newc = i, j
                    for kk in range(k): # k까지 이동 가능
                        newr, newc = newr+digonalr[diretion], newc+digonalc[diretion]
                        if 0<=newr<n and 0<=newc<n:
                            if treemap[newr][newc] >0:
                                tempcount +=treemap[newr][newc] # 죽인 나무 수 count
                                temppoints.append((newr,newc))# 간 위치 추가
                            elif treemap[newr][newc] ==0:
                                # 중간에 제초제나 빈칸이면 point는 append
                                temppoints.append((newr,newc))# 간 위치 추가
                                break
                            elif treemap[newr][newc] ==-1:
                                # 벽 만나면
                                break
                        else: break # 범위 넘어가는 순간 다른 방향으로
            if maxcount<tempcount: # 한 점에 대해 분석 끝내면, 비교해서 max update
                maxcount=tempcount
                points = temppoints

    return [maxcount, points]

# 4) herbicide ---------
def herbicide():
    """
    제초제 뿌리기
    1) 원래 있던 제초제 -1
    2) 제초제 뿌려질 위치 받아온 것 -> 값 세팅
    """
    global treemap, herbicidemap
    # 위치 받기
    current_deadtreecount, points =herbicide_search()
    # 전 제초제 -1
    for i in range(n):
        for j in range(n):
            if herbicidemap[i][j]>0:
                herbicidemap[i][j] -=1
    # 새 제초제 뿌리기 - 제초제 map, treep map
    for p in points:
        i, j = p
        herbicidemap[i][j] = c
        treemap[i][j] =0 # 나무 사라짐

    return current_deadtreecount
# main
deadtreecount =0
for i in range(m):
    # m년동안 박멸
    grow()
    multiplicate()
    current_deadtreecount= herbicide()
    deadtreecount+=current_deadtreecount

print(deadtreecount)