[Samsung] 2022-1 오후 2번 나무 박멸

March 31, 2023

[Samsung] 2022-1 오후 2번 나무 박멸

Question

Language: Python

Difficulty: Gold 4

해당 문제는 주어진 문제의 시뮬레이션을 구현하는 문제이며 bfs가 활용된다.

시뮬레이션 과정은 아래와 같다.

나무의 성장
나무의 번식
제초제 살포

각 과정들을 살펴보자

나무의 성장

나무가 있는 칸을 기준으로 인접한 칸들을 조사하여 해당 칸 수 만큼 나무의 값을 증가시킨다.

def tree_grow():
global tree_map
for row in range(n):
    for col in range(n):
        #나무가 있는 경우
        if tree_map[row][col] > 0:
            count=0
            for dir in range(4):
                next_row=row+dy[dir]
                next_col=col+dx[dir]

                #격자를 벗어나는 칸
                if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                    continue

                #나무가 있는 경우
                if tree_map[next_row][next_col] >0:
                    count+=1
            
            #나무가 있는 인접한 칸의 갯수만큼 성장한다.
            tree_map[row][col]+=count

나무의 번식

모든 나무는 동시에 번식을 진행한다. 따라서, 하나씩 처리를 하게 되면 overwrite 되는 문제가 발생하여 올바르지 않은 결과가 도출된다. 따라서, 동시에 번식을 적용하기 위해 tree_map을 새로 구현해서 해당 배열에 저장한다.

우선적으로, 각 나무에 대해 나무가 있는 인접한 칸들을 조사한다. 이후, 인접한 칸들에 대해서, 기존의 나무가 있던 칸의 나무의 값 // 인접한 나무가 있는 칸의 갯수만큼을 더해주도록 한다.

def tree_reproduce():
    global tree_map

    new_tree_map=get_new_map()
    reproduce_infos=[]
    for row in range(n):
        for col in range(n):
            if tree_map[row][col] > 0:
                count=0
                candidates=[]
                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    #격자를 벗어나는 칸
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        continue

                    #벽인 경우
                    if tree_map[next_row][next_col] ==-1:
                        continue

                    #빈칸이면서, 제초제가 없는 칸인 경우
                    if tree_map[next_row][next_col] ==0 and pepticide_map[next_row][next_col] ==0:
                        count+=1
                        candidates.append((next_row,next_col))

                new_tree_map[row][col]+=tree_map[row][col]
                #인접한 칸에 대해서 번식 진행
                for next_row,next_col in candidates:
                    new_tree_map[next_row][next_col]+=(tree_map[row][col]//count)

    trees=[]     
    #새로운 tree_map을 저장
    for row in range(n):
        for col in range(n):
            if new_tree_map[row][col] > 0:
                trees.append((row,col))
            tree_map[row][col]=new_tree_map[row][col]
    
    return trees

제초제 살포

우선, 기존에 제초제가 살포되었던 자리의 제초제값을 1씩 감소시키도록 한다. 제초제는 최대 c 년동안 남아있기 때문에 이를 반영한다.

제초제는 가장 많은 수의 나무를 죽일 수 있는 칸 중에서 행,열이 가장 작은 좌표에 살포되어야 하므로 모든 좌표에 대해 제초제를 살포했을때의 박멸되는 나무의 갯수를 조사해서 적합한 좌표를 구한다. 이후, 해당 좌표에 제초제를 살포하는 작업과 해당 자리의 나무를 박멸하는 작업을 진행한다.

def pepticide(trees):
    global tree_map,pepticide_map

    #우선 기존의 pepticide map의 제초제의 기간 단축
    for row in range(n):
        for col in range(n):
            if pepticide_map[row][col] >0:
                pepticide_map[row][col]-=1
    
    #가장 효과적인 행,열을 찾기 위해 나무가 있는 칸에 대해 조사 시작
    candidates=[]
    #대각선 방향 이동
    pep_dy=[-1,-1,1,1]
    pep_dx=[-1,1,1,-1]
    #가장 효과적인 제초제 살포 위치를 찾기 위해 나무가 있는 좌표에 대해 제초제를 뿌려보면서 조사한다.
    for start_row in range(n):
        for start_col in range(n):

            #벽이거나 빈칸 인경우에는 해당 칸에만 제초제 뿌려진다.
            if tree_map[start_row][start_col]==-1 or tree_map[start_row][start_col]==0:
                candidates.append((0,start_row,start_col))
                continue
            
            count=tree_map[start_row][start_col]
            for dir in range(4):
                for i in range(1,k+1):
                    next_row=start_row+pep_dy[dir]*i
                    next_col=start_col+pep_dx[dir]*i

                    #격자를 벗어나는 경우 더 이상 탐색 하지 않는다.
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        break
                    
                    #벽이거나 빈칸이면 더 이상 제초제 진행 X
                    if tree_map[next_row][next_col]==-1 or tree_map[next_row][next_col]==0:
                        break
                    
                    count+=tree_map[next_row][next_col]
            candidates.append((count,start_row,start_col))

    candidates.sort(key=lambda x: (-x[0],x[1],x[2]))
    #가장 많은 나무를 박멸하면서, 행,열이 가장 작은 좌표에 제초제를 살포한다.
    dead_tree_count,start_row,start_col=candidates[0]

    #나무 박멸 진행 및 제초제 살포 진행
    tree_map[start_row][start_col]=0
    pepticide_map[start_row][start_col]=c
    for dir in range(4):
        for i in range(1,k+1):
            next_row=start_row+pep_dy[dir]*i
            next_col=start_col+pep_dx[dir]*i

            #격자를 벗어나는 경우 더 이상 탐색 하지 않는다.
            if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                break
            pepticide_map[next_row][next_col]=c
            #빈칸 이거나, 나무가 없으면 더 이상 제초제 진행 X
            if tree_map[next_row][next_col]==-1 or tree_map[next_row][next_col]==0:
                break
            
            tree_map[next_row][next_col]=0
            pepticide_map[next_row][next_col]=c
    
    return dead_tree_count

Solution

from collections import deque
#나무의 성장
def tree_grow():
    global tree_map
    for row in range(n):
        for col in range(n):
            #나무가 있는 경우
            if tree_map[row][col] > 0:
                count=0
                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    #격자를 벗어나는 칸
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        continue

                    #나무가 있는 경우
                    if tree_map[next_row][next_col] >0:
                        count+=1
                
                #나무가 있는 인접한 칸의 갯수만큼 성장한다.
                tree_map[row][col]+=count

#모든 나무의 번식 정보를 동시에 반영하기 위해 새로운 tree_map 배열 생성, 벽 정보만 초기화 시킨다.
def get_new_map():
    new_tree_map=[[0] * n for _ in range(n)]
    for row,col in walls:
        new_tree_map[row][col]=-1
    return new_tree_map

#나무의 번식
def tree_reproduce():
    global tree_map

    new_tree_map=get_new_map()
    reproduce_infos=[]
    for row in range(n):
        for col in range(n):
            if tree_map[row][col] > 0:
                count=0
                candidates=[]
                for dir in range(4):
                    next_row=row+dy[dir]
                    next_col=col+dx[dir]

                    #격자를 벗어나는 칸
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        continue

                    #벽인 경우
                    if tree_map[next_row][next_col] ==-1:
                        continue

                    #빈칸이면서, 제초제가 없는 칸인 경우
                    if tree_map[next_row][next_col] ==0 and pepticide_map[next_row][next_col] ==0:
                        count+=1
                        candidates.append((next_row,next_col))

                new_tree_map[row][col]+=tree_map[row][col]
                #인접한 칸에 대해서 번식 진행
                for next_row,next_col in candidates:
                    new_tree_map[next_row][next_col]+=(tree_map[row][col]//count)

    trees=[]     
    #새로운 tree_map을 저장
    for row in range(n):
        for col in range(n):
            if new_tree_map[row][col] > 0:
                trees.append((row,col))
            tree_map[row][col]=new_tree_map[row][col]
    
    return trees

def pepticide(trees):
    global tree_map,pepticide_map

    #우선 기존의 pepticide map의 제초제의 기간 단축
    for row in range(n):
        for col in range(n):
            if pepticide_map[row][col] >0:
                pepticide_map[row][col]-=1
    
    #가장 효과적인 행,열을 찾기 위해 나무가 있는 칸에 대해 조사 시작
    candidates=[]
    #대각선 방향 이동
    pep_dy=[-1,-1,1,1]
    pep_dx=[-1,1,1,-1]
    #가장 효과적인 제초제 살포 위치를 찾기 위해 나무가 있는 좌표에 대해 제초제를 뿌려보면서 조사한다.
    for start_row in range(n):
        for start_col in range(n):

            #벽이거나 빈칸 인경우에는 해당 칸에만 제초제 뿌려진다.
            if tree_map[start_row][start_col]==-1 or tree_map[start_row][start_col]==0:
                candidates.append((0,start_row,start_col))
                continue
            
            count=tree_map[start_row][start_col]
            for dir in range(4):
                for i in range(1,k+1):
                    next_row=start_row+pep_dy[dir]*i
                    next_col=start_col+pep_dx[dir]*i

                    #격자를 벗어나는 경우 더 이상 탐색 하지 않는다.
                    if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                        break
                    
                    #벽이거나 빈칸이면 더 이상 제초제 진행 X
                    if tree_map[next_row][next_col]==-1 or tree_map[next_row][next_col]==0:
                        break
                    
                    count+=tree_map[next_row][next_col]
            candidates.append((count,start_row,start_col))

    candidates.sort(key=lambda x: (-x[0],x[1],x[2]))
    #가장 많은 나무를 박멸하면서, 행,열이 가장 작은 좌표에 제초제를 살포한다.
    dead_tree_count,start_row,start_col=candidates[0]

    #나무 박멸 진행 및 제초제 살포 진행
    tree_map[start_row][start_col]=0
    pepticide_map[start_row][start_col]=c
    for dir in range(4):
        for i in range(1,k+1):
            next_row=start_row+pep_dy[dir]*i
            next_col=start_col+pep_dx[dir]*i

            #격자를 벗어나는 경우 더 이상 탐색 하지 않는다.
            if next_row < 0 or next_row >=n or next_col < 0 or next_col>=n:
                break
            pepticide_map[next_row][next_col]=c
            #빈칸 이거나, 나무가 없으면 더 이상 제초제 진행 X
            if tree_map[next_row][next_col]==-1 or tree_map[next_row][next_col]==0:
                break
            
            tree_map[next_row][next_col]=0
            pepticide_map[next_row][next_col]=c
    
    return dead_tree_count

def print_board(title,board):
    print(title)
    for row in board:
        print(*row)

def solution():
    sum_of_dead=0
    for i in range(m):
        tree_grow()
        trees=tree_reproduce()
        sum_of_dead+=pepticide(trees)
    
    print(sum_of_dead)
    
if __name__ == "__main__":
    n,m,k,c=map(int,input().split())
    tree_map=[list(map(int,input().split())) for _ in range(n)]
    pepticide_map=[[0] * n for _ in range(n)]
    walls=[]
    #벽의 좌표 초기화
    for row in range(n):
        for col in range(n):
            if tree_map[row][col] == -1:
                walls.append((row,col))

    dy=[-1,0,1,0]
    dx=[0,1,0,-1]

    solution()

Twitter Facebook LinkedIn

Jehyun Jung

[Samsung] 2022-1 오후 2번 나무 박멸

[Samsung] 2022-1 오후 2번 나무 박멸

Question

Language: Python

Difficulty: Gold 4

Solution

공유하기

댓글남기기

참고

Typescript Module Issue

Changing Java Version in Linux

[BOJ] Q1725 히스토그램

[Programmers] Q176962 과제 진행하기