[2022 삼성 코딩테스트 상반기 오후 2번] 코드트리 - 나무 박멸 파이썬 리뷰

골드4 문제

 

https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all?&utm_source=clipboard&utm_medium=text 

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

 

이문제는 예상외로 구상하고 예외케이스만 조금 조심하니까 

다른문제에 비해서 금방 풀렸다.

 

 

하.. 작년 하반기 준비하면서 분명 못풀어서 징징대던 문제같은데.. 

실제로 2번에서 막혔었고..

 

작년에 어떻게 풀었나 코드를 보니까

 

진짜 토악질나왔다 ㅋㅋ 

무슨뭐.. 2차원배열을 3개를 쓰고.. 아주 앰뱅났다..

 

 

이번 문제에서 딱히 막히는건 없었다. 

 

역시나 국어 문제로 조금 시간이 걸렸고..

 

제초제가 영향을 미치는게 한칸더 가는 처리 , 그리고 제초제를 행작음,열작음 우선순위로 값을 가지는것. for문으로 했는데

break를 1번밖에 안걸어서 다시 for i 탐색이 시작돼서 문제가 발생했다. 이부분은 참 고민이다.

 

특히나 2중 포문중에 어느 특정 i,j 값이 왔을때 나는 possible =True 로 해서 비교군으로 탈출시켰는데

더좋은 방법이 있을까? 궁금하다. 이건 코드트리 질문에 남겨봐야지. 

 

 

조금 조심하는 부분이 이제 

 

어느 방향으로 진행하다가 벽이나 아무것도 없는공간이라 막히면 그쪽 제초제 탐색을 멈추는것 정도? 

이거는 

dx,dy 탐색 후 거리 탐색 k 를 넣으면 되는걸로 진행하니 잘됐다.  

 

조금 특이한건, 

제초제 배열과 진짜_제초제 배열을 따로 둬서 

진짜 제초제 부분을 -1 씩 해주고 만약 제초제 배열 값이 있다면 진짜_제초제에 덮어 씌우고 하는식으로

문제조건을 만족 시켰다.

 

이부분을 생각하느라 어라? 처음부터 다시해야하나 했는데 

잘생각하니 풀수 있었다..

 

작년 코드하고 비교해보니 확실히 진화한게 느껴져서 굉장히 기분이 좋은하루였다. 

 

꼭 위에 이중포문 탈출 방법을 물어봐야겟다. 

 

 

from collections import deque import sys #sys.stdin = open("input_namu.txt",'r') n,m,k,c = map(int,input().split()) maps = [ list(map(int,input().split())) for _ in range(n)] zechoze = [ [0]*n for _ in range(n)] deb = 0 real_zechoze = [ [0]*n for _ in range(n)] dxs=[0,0,-1,1] dys=[1,-1,0,0] def in_range(x,y) :     return 0<= x < n and 0<= y < n def grow():     for i in range(n) :         for j in range(n) :             if maps[i][j] > 0 : # 1이상이면,                 tree_add = 0                 for k in range(4) :                     nx,ny = i+dxs[k],j+dys[k]                     if in_range(nx,ny) and maps[nx][ny] >= 1: # 나무가 하나라도있으면                         tree_add += 1                 maps[i][j] += tree_add     return def bunsik():     next_maps = [ [0]*n for _ in range(n)]     global maps     for i in range(n) :         for j in range(n) :             if maps[i][j] > 0 : # 나무 발견시 십자방향으로 더하기                 tree_cnt = 0                 next_maps[i][j] = maps[i][j]                 for k in range(4) :                     nx,ny = i+dxs[k],j+dys[k]                     if in_range(nx,ny) and maps[nx][ny] ==0 and real_zechoze[nx][ny] == 0: # 나무가 하나라도있으면                         tree_cnt += 1                 for t in range(4) :                     nx,ny = i+dxs[t],j+dys[t]                     if in_range(nx,ny) and maps[nx][ny] ==0 and real_zechoze[nx][ny] == 0: # 나무가 하나라도있으면                         next_maps[nx][ny] += (maps[i][j]//tree_cnt)             else :                 next_maps[i][j] += maps[i][j]     maps=next_maps.copy()     return def find_zecho(x,y):     global maps, zechoze     zechoze = [ [0]*n for _ in range(n)]     #k방향 만큼 전파. 그러다 막히면 그방향으로는 멈춘다.     # 단 전파되는 도중 벽이 있거나 나무가 아얘 없는 칸이 있는 경우, 그 칸 까지는 제초제가 뿌려지며 그 이후의 칸으로는 제초제가 전파되지 않습니다.     zecho_cnt = 0     ddx=[-1,-1,1,1]     ddy=[-1,1,-1,1]     zecho_cnt += maps[x][y]     zechoze[x][y] = c     for i in range(4):         x1,y1 = x,y         for _ in range(k):             nx,ny = x1+ddx[i],y1+ddy[i]             if in_range(nx,ny) and maps[nx][ny] > 0 :                 x1,y1 = nx,ny                 zecho_cnt += maps[nx][ny]                 zechoze[nx][ny] = c                 #print(i,'번째',nx,ny,maps[nx][ny],'확인')             elif in_range(nx,ny) and maps[nx][ny] == 0 : #막혀있는곳일때 거기까진 제초제 묻히고 짜른다.                 zechoze[nx][ny] = c                 #print(nx,ny,maps[nx][ny],'확인')                 break             else : #벽의 경우 제초제를 뿌려도 의미가 없다.                 break     #print(zecho_cnt,x,y)     return zecho_cnt def zecho_kill() :     global zechoze     for i in range(n) :         for j in range(n) :             if zechoze[i][j] > 0 :                 maps[i][j] = 0     return def zecho_time():     #먼저 시간 지나가게 한다.     for i in range(n) :         for j in range(n):             if real_zechoze[i][j] > 0 :                 real_zechoze[i][j] -= 1 # 1시간씩 빼주기.             if zechoze[i][j] > 0 : # 제초가있다면                 real_zechoze[i][j] = zechoze[i][j]     return def zecho():     tree_cnt = 0     max_zecho = [ [0]*n for _ in range(n)] # 맥스 제초 칸을 나타낸다.     max_zecho_cnt = 0     for i in range(n) :         for j in range(n) :             if maps[i][j] > 0 :                 max_zecho[i][j] = find_zecho(i,j)                 max_zecho_cnt= max(max_zecho_cnt,max_zecho[i][j])     if deb:         print('각 칸은 제거가능한 최대 나무수')         for kx in max_zecho:             print(*kx)                 print('최대 지울수잇는 나무 ',max_zecho_cnt)     possible = False     for i in range(n) :         for j in range(n):             if max_zecho[i][j] == max_zecho_cnt :                 if deb:                     print(i,j,'에서 제초시작')                 find_zecho(i,j) # zecho에 리얼 제초제 위치가 들어온다.                 possible = True                 break         if possible :             break     #제초제 새로운거 반영시키기 + 제초제 뿌리면서 제초제 시간 없어지기.     if deb:         print('제초제 킬하기전 ')         for kx in zechoze:             print(*kx)         print('리얼제초')         for kx in real_zechoze:             print(*kx)     zecho_time()     #제초제 대로 maps에 반영한다.     zecho_kill()     if deb:         print('제초제 킬하고난다음 ')         for kx in zechoze:             print(*kx)         print('리얼제초')         for kx in real_zechoze:             print(*kx)         for kx in maps:             print(*kx)     #조건이 많음.     #1.가장 많이 박멸되는 제초제 위치에 뿌린다. 많이 박멸되는게 여러개면 행작고, 그다음 열작고 순서 (걍 정렬써도될듯 )     #2.제초제는 대각방향으로 k칸 만큼 전파된다. (벽이나 없는공간 무시 )     #3.제초제는 c년만큼 남아있음. 이때 이곳엔 나무가 자라날 수 없다. 제초 남은 시간을 숫자로 관리한다. 새로 덮어씌우는건 걍 = 으로 덮어씌우기.     #이때 박멸한 나무수를 return 해야한다.     return max_zecho_cnt def debug(t):     print(t,'번째')     for k in maps:         print(*k)     print()     return answer = 0 for _ in range(m) :     if deb:         debug('성장전')     grow() # 나무의 성장     if deb:         debug('성장후')     bunsik() # 나무의 번식 3칸이 가능하면 가운데//3, 2칸이 가능하면 가운데//2 로 생겨난다. 동시에 이뤄지며, 이때 겹쳐지면 더해지기로 해야한다.     if deb:         debug('번식 후')     answer += zecho() # 나무 제초제 뿌리기. 대각선으로 진행. c년만큼 제초제가 남아있고 c+1년되면 없어진다. 새로 뿌려지면 덮어 씌워진다. 여기서 조건이 많으니 더 자세한건 안에서 쓰자. print(answer)