코드트리 나무박멸 | python | just 구현

문제

링크

풀이

특별한 테크닉 없이 문제에서 주어진 상황대로 함수화해서 짜면 된다. 실제로 구현할 때에도 막힘 없이 1시간 내로 풀이해서 제출하였다. 그러나 역시나 한 번에 성공하지 못했고 예외 처리 안 한 부분이 한 곳 있어서 정답을 맞추지 못했던 것 같다

사용한 배열

board : 나무 & 벽 & 빈칸이 저장되어 있는 2차원 배열 (NxN)
herb: 제초제 존재 여부를 확인하는 2차원 배열 (NxN)

제초제가 뿌려진 칸에는 c년만큼 제초제가 남아있다가 c+1년째가 될 때 사라지게 되는 로직은 마법사 상어와 복제 에서 물고기 냄새칸을 구하는 로직과 동일해서 매우 빠르게 풀었지만 해당 문제를 풀지 않았다면 살짝은 헤맸을 것 같다

막혔던 곳

각 칸 중 제초제를 뿌렸을 때 나무가 가장 많이 박멸되는 칸이 없는 경우
spray_herb() 과정을 진행시키면 안된다. 따라서 해당 부분에 대한 조건 처리를 해주었더니 성공했다

def spray_herb(max_loc,max_total):
    sy,sx=max_loc
    if max_total==-1:
        return
	(생략)

전체 코드

N,M,K,C= map(int,input().split())
result=0
board=[] # 나무 & 벽 & 빈칸이 저장되어 있는 2차원 배열
for _ in range(N):
    board.append(list(map(int,input().split())))
herb=[[0]*N for _ in range(N)] # 제초제 여부

dd=[(-1,-1),(-1,1),(1,-1),(1,1)] # 대각선 방향
d=[(1,0),(-1,0),(0,-1),(0,1)] # 상하좌우

def grow_tree():
    for i in range(N):
        for j in range(N):
            if board[i][j]>0 : # 나무라면
                for dy, dx in d:
                    Y=i+dy
                    X=j+dx
                    if 0<=Y<N and 0<=X<N and board[Y][X]>0: # 인접한 칸에 나무가 있다면
                        board[i][j]+=1

def print_board():
    for i in range(len(board)):
        print(board[i])
    print('-----')

def breed_tree():
    temp=[[0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if board[i][j]>0: #나무라면
                cnt=0
                candidate=[]
                for dy, dx in d:
                    Y=i+dy
                    X=j+dx
                    if 0<=X<N and 0<=Y<N and board[Y][X]==0 and herb[Y][X]==0:
                        candidate.append((Y,X))
                        cnt+=1
                if cnt==0:
                    continue
                treeNum=board[i][j]//cnt
                for y,x in candidate:
                    temp[y][x]+=treeNum

    for i in range(N):
        for j in range(N):
            board[i][j]+=temp[i][j]

def select_herb_space():
    max_total=-1
    max_loc=(-1,-1)
    for i in range(N):
        for j in range(N):
            if board[i][j]>0: # 나무라면
                deadTreeNum=board[i][j]
                for dy, dx in dd:
                    y, x = i, j
                    for _ in range(K):
                        Y=dy+y
                        X=dx+x
                        if 0<=Y<N and 0<=X<N and board[Y][X]>0:
                            y=Y
                            x=X
                            deadTreeNum+=board[Y][X]
                        else:
                            break
                if max_total<deadTreeNum:
                    max_total=deadTreeNum
                    max_loc=(i,j)
    return max_loc,max_total

def spray_herb(max_loc,max_total):
    sy,sx=max_loc
    if max_total==-1:
        return
    global result
    result+=max_total
    board[sy][sx]=0 # 본인 나무 먼저 박멸
    herb[sy][sx]=C+1
    for dy, dx in dd:
        y, x = sy, sx
        for _ in range(K):
            Y = dy + y
            X = dx + x
            if 0 <= Y < N and 0 <= X < N :
                if board[Y][X] > 0:
                    board[Y][X]=0 # 나무 박멸
                    herb[Y][X] = C + 1
                    y=Y
                    x=X
                elif board[Y][X]==-1 or board[Y][X]==0:
                    herb[Y][X] = C + 1
                    break
            else:
                break

def remove_herb():
    for i in range(N):
        for j in range(N):
            if herb[i][j]>0:
                herb[i][j]-=1
def print_herb():
    for i in range(N):
        print(herb[i])

for _ in range(M):
    grow_tree()
    # print_board()
    breed_tree()
    # print_board()
    max_loc,max_total=select_herb_space()
    spray_herb(max_loc,max_total)
    # print_board()
    # print_herb()
    remove_herb()

print(result)

기출 풀면서 1트에 성공한 적이 거의 손에 꼽아서 조금 두렵다. 시험장에선 TC가 10개니까 어떻게든 하나씩 손으로 풀어보고 하면 예외에 해당하는 부분을 찾을 수 있을 것이라 생각한다. 아무튼 뇌에 힘 빡 주고 예외처리 하는 것에 조금 더 집중해야겠다. 1문제 3시간 안에 완벽히 풀이해야 겠다는 생각으로 !

사실 이 정도로 나오면 절하면서 당당히 1솔하고 나올 수 있을것 같다
오후 1번 문제 제발 술술 풀리길