[코드트리] 나무박멸(파이썬) -2022 삼성sw 상반기 코테 기출

https://www.codetree.ai/frequent-problems/tree-kill-all/description

코드트리

삼성코태 중 전형적인 구현문제.

 

우선 저는 이 문제를 풀 때

어떻게하면 시간도 같이 줄일지 생각도 많이 했습니다.

 

저는 성장과 번식을 동시에 진행해줬습니다.

새로 옮길 new_room을 deepcopy한 다음에

성장-->인접한 곳 찾고 

new_room에서 해당 지점더하기

번식-->나무없고 살충제 없는 곳의 숫자 구하고

현재지점 나무 나눈 만큼

new_room에 비어있는 지점에 그 수를 더해준다

 

번식할 때 더해주는 게 중요.

'동시에'퍼지기 때문에

위 아래 동시에 퍼지는 게 겹치는 경우에는 합해줍니다.

 

그 다음 살충제 뿌리기.

room을 다 돌면서 나무가 있는지 여부를 확인하면

시간초과가 뜰 거 같았어요.

그래서 성장&번식에서

기존나무+추가된 나무를 리스트로 받아주고

sort시킨 후에 살충제를 뿌릴 지점을 구했어요.

원래는 집합으로 받으려했는데

문제 조건에서

'만약 잡을 수 있는 나무가 같다면

행열이 앞서는 순으로'라는 표현이 있어서

리스트로 받은 후 sort하는 게 편하다 생각했어요.

(집합은 정렬기능은 없네요)

해당 지점을 찾은 후에

살충제를 뿌려줍니다.

 

많은 분들이 해가 바뀔 때마다 

살충제를 하나씩 지워나가는 걸 택하실 겁니다.

저도 처음에 그 생각을 했었는데

m과 n이 점점 커질수록

그렇게하면 시간초과 이슈가 생길 수 있었습니다.

그래서 살충제를 뿌릴 때

'현재 년도+지속시간'을 해줬습니다.

이후, 번식을 할 때

현재 년도가 현재 지점 살충제보다 크다면

살충제가 사라진 거나 마찬가지이므로

굳이 for문을 여러개 돌리지 않고 구해줬습니다.

 

그리고 많은 분들+저또한 헤맨 부분.

코드 트리상에서 이 부분이 제대로 구현되지 않았다면

테케7에서 틀렸다고 뜰 겁니다.

저도 상당히 이것 떄문에 골치 아팠는데...

질문게시판 보고 알았습니다.

 

살충제의 조건 중 주의할 점.

벽이나 나무가 없다면

그 칸까지만 퍼지고 

전파되지 않는다는 것.

벽이야 어처피 나무가 안자라니 무시해도 되는데

나무가 없는 칸도 뿌려야한다는 게 

생각이 잘 안날 조건.

나무가 없는 칸까지만 뿌렸다가 멈춘다는 것이 포인트.

from copy import deepcopy
N,M,K,C=map(int,input().split())
dx=[0,0,1,-1]
dy=[1,-1,0,0]

sx=[1,1,-1,-1]
sy=[1,-1,1,-1]

room=[list(map(int,input().split())) for _ in range(N)]
spray=[[-1]*N for _ in range(N)]
answer=0

def inside(x,y):
    if x<0 or x>=N or y<0 or y>=N:
        return False
    return True

for year in range(M):
    new_room=deepcopy(room)
    now_tree=[]
    #1 나무 성장 &2 나무 번식
    for x in range(N):
        for y in range(N):
            if room[x][y]>0:
                if not (x,y) in now_tree:
                    now_tree.append((x,y))
                cnt=0
                go=0
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]
                    if inside(nx,ny):
                        if room[nx][ny]>0:
                            cnt+=1
                        elif room[nx][ny]==0 and spray[nx][ny]<year:
                            go+=1
                new_room[x][y]+=cnt

                if go==0:
                    continue

                div=new_room[x][y]//go
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]
                    if inside(nx,ny) and room[nx][ny]==0 and spray[nx][ny]<year:
                        new_room[nx][ny]+=div
                        if not (nx,ny) in now_tree:
                            now_tree.append((nx,ny))
    room=deepcopy(new_room)
    #print(room)
    #3.제초제
    #3-1 살균지역 설정
    if not now_tree:
        continue
    m_kill=0
    kx,ky=-1,-1
    now_tree.sort()
    for tx,ty in now_tree:
        n_kill=room[tx][ty]

        for d in range(4):
            nx=tx+sx[d]
            ny=ty+sy[d]
            count=0
            while count<K and inside(nx,ny) and room[nx][ny]>0:
                n_kill+=room[nx][ny]

                nx+=sx[d]
                ny+=sy[d]
                count+=1

        if n_kill>m_kill:
            m_kill=n_kill
            kx,ky=tx,ty

    #3-2살충재 살포

    now_cut=room[kx][ky]
    room[kx][ky]=0
    spray[kx][ky]=year+C

    for d in range(4):
        nx=kx+sx[d]
        ny=ky+sy[d]
        count=0
        while count<K and inside(nx, ny):
            if room[nx][ny]==0 or room[nx][ny]==-1:
                spray[nx][ny]=year+C
                break
            now_cut+=room[nx][ny]
            room[nx][ny]=0
            spray[nx][ny]=year+C
            nx += sx[d]
            ny += sy[d]
            count+=1
    # print(spray)
    # print(now_cut)
    answer+=now_cut

print(answer)

 

문제 자체의 구현 난이도도 빡세지만

작은 조건 하나 놓쳐서 많이 헤맨 문제.

실전에서 막히면

'혹시 내가 조건 뭐 빠진거 없나'

1.범위

2.변수

3.구현조건

이렇게 봐야겠네요.