[코테준비] 삼성16. 코드트리: 포탑 부수기 python

왜인지, 계속 포탑이 아니라 포탄으로 읽게 되는.. 포탑 부수기 문제이다! 근데, 코드트리 토론창에 답글을 달아주시는 관리자 같으신 분은 어떤 분이실까? 정말 답글이 빨리 달리고 내가 푼 문제에 답글을 달아주시는 분은 다 그분이다. 주말인데도 빨리 답글을 달아주신다. 각 문제당 당담자가 있는 것 일까? 어째든 답글을 달아주셔서 매우 감사하다. 

---

포탑 부수기

• 링크: https://www.codetree.ai/training-fihttps://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description 
• 기출: 삼성 SW 역량테스트 2023 상반기 오전 1번 문제
• 난이도:골드 1
• 분류: 시뮬레이션, BFS
• 직접 푼 여부: O  (문제이해: 30m, 코드 틀 짜기: 60m, 코드 짜기: 60m,  디버깅 120m 이상) 
• 언어: 파이썬

풀이 노트

아래 사진은 내가 풀며 정리한 노트이다. 만약 아래 노트가 이해가 안되거나 보기 싫으면 아래 코드만 보아도 될 것이다. 주석을 최대한 많이 달아놨다. 

• 연필: 문제를 보면서 적은 것
• 검정펜: 어떻게 풀어가야할지 계획
• 파란펜: 주의해야할 것
• 빨간펜: 놓쳐서 디버깅 때 찾은 것 & 공부해야할 것 

문제 이해

문제 이해 및 틀

내가 놓쳤던 부분은 다음과 같다. 

1. attacker / target 을 정할 때, attacker의 history를 보아야하는데, 그냥 바로 전에 공격했는지만 체크했다. - 이 history는 2차원 n*m 배열로 처리하면 좋다. 몇 번째 loop에 attacker였는지 기록 (나는 이걸 for kk in k 라고 해놓고, 코드에 kk+1이 아닌 k+1라고 해서 또 한번 틀렸다. - 테케 5에서 걸렸던 것 같다. 아닐지도.)
2. bfs는 dfs와 다르게 한칸씩 늘려나가는 것이므로 level을 기록하며 최소를 잡을 필요가 없다. - 그냥 젤 먼저 도착하면 그게 최단 거리 !  그게 bfs인것인데 너무 dfs만 쓰다가 까먹었다. 그래서 코드를 쓰며 좀 애먹었다. 
3. 레이저가 아닌 포탄 공격을 할 때, 주변 8방향에 영향을 끼친다.  분명 써놨는데, 코딩할 때는 4방향으로 해서 테케3에서 계속 걸렸다. 

정답 코드 💻

# 포탑 부수기
import sys
import copy # attack 관련 요소들 기록용 array
from collections import deque

input = sys.stdin.readline
# input --------------------------------
n,m,k = map(int,input().split())
grid = [list(map(int, input().split())) for _ in range(n)]


# def --------------------------------
# [1] attacker 선정, 핸디캡 [ok]
def attacker_choose():
    global attack_related, grid
    # attacker 선정
    point=5001 # min을 찾아야하므로, max보다 더 큰 값으로 설정
    ar= ac = 0
   # 1) min
    for i in range(n):
        for j in range(m):
            if grid[i][j]>0 and grid[i][j]<point:
                ar, ac =i, j
                point = grid[i][j]
            elif grid[i][j] == point:
                # 2) history 확인
                if attacker_history[i][j] > attacker_history[ar][ac]: # 최근이면 값이 더 큼
                    ar, ac = i,j
                elif attacker_history[i][j]== attacker_history[ar][ac]: # 같으면 더 비교해야함
                    if i+j > ar+ac :
                        ar, ac = i, j
                    elif i+j == ar+ac:
                        if j>ac:
                            ar, ac = i, j
    attack_related[ar][ac] = True
    attacker_history[ar][ac] = kk+1
    grid[ar][ac] += m+n
    return (ar,ac)

# [2] target 선정  & 공격
def target_choose_attack(attacker):
    global attack_related, grid, attacker_history
    # * attacker빼고
    # 0) target 선정 [ok]
    # (1) max
    point = 0 # 0보단 커야함
    tr=tc = 0 # attacker 위치
    for i in range(n):
        for j in range(m):
            if grid[i][j] >0 and grid[i][j] >point and (i,j) != attacker:
                point = grid[i][j] # point update
                tr, tc = i, j # 위치 업데이트
            elif grid[i][j] ==point and (i,j) != attacker:
                # (2) history
                if attacker_history[i][j] < attacker_history[tr][tc]:
                    tr, tc = i, j
                elif attacker_history[i][j] == attacker_history[tr][tc]:
                    if i+j < tr+tc:
                        tr, tc = i,j
                    elif i+j == tr+tc:
                        if j<tc:
                            tr, tc = i, j
    target = (tr,tc)
    attack_related[tr][tc] = True

    #2) 공격
    if not laser(attacker, target):
        shoot(attacker, target)
    return 

# [2-1] laser & 포탄 부서짐(0이하면 0으로) [ok]
def laser(attacker, target):
    # 1. attack related 표시
    global attack_related, grid
    laser_visted = [[False] * m  for _ in range(n)]
    laser_visted[attacker[0]][attacker[1]] = True
    route=[] # 길 알아야하므로
    q = deque()
    q.append((attacker,route))

    while q:
        (r, c), nowroute = q.popleft()
        for i in range(4):
            newr, newc = (r+ dr[i])%n, (c + dc[i])%m
            if laser_visted[newr][newc] or grid[newr][newc]<=0: continue # 안되는 상황은 넘김
            # 도착하면, 1) target point 빼기, 2) route 포인트 빼기
            if (newr,newc) == target:
                point = grid[attacker[0]][attacker[1]]
                grid[target[0]][target[1]] = max(0,grid[target[0]][target[1]]-point) # 1)
                for rr, cc in nowroute: #2)
                    grid[rr][cc]=max(0, grid[rr][cc]-point//2)
                    attack_related[rr][cc] =True
                return True

            # 도착안하면, route업데이트
            temproute = copy.deepcopy(nowroute)
            temproute.append((newr,newc))
            laser_visted[newr][newc] =True # 위에서 pop 후에 True하면, 그 q가 나오기 전에 search에 활용될 수 있음
            q.append(((newr,newc), temproute))

    return False # 끝까지 왔으면, 레이저 불가



# [2-2] shoot & 포탄 부서짐 (0이하면 0으로) [ok]
def shoot(attacker, target):
    # 1. attack related 표시
    global attack_related, grid
    point = grid[attacker[0]][attacker[1]]
    grid[target[0]][target[1]] = max(0, grid[target[0]][target[1]]-point)
    for i in range(8):
        newr, newc = (target[0]+drr[i])%n, (target[1]+dcc[i])%m
        if grid[newr][newc]>0 and (newr,newc) !=attacker:
            grid[newr][newc] = max(0, grid[newr][newc]-point//2)
            attack_related[newr][newc] = True
    return


# [4] resetting
def resetting():
    #resetting하며, 부서지지 않은 포탑이 하나 뿐이면, 중지 시키기
    global grid
    cnt =0
    for i in range(n):
        cnt+=grid[i].count(0)
        for j in range(m):
            if grid[i][j] >0 and not attack_related[i][j]:
                grid[i][j]+=1
    if cnt>=m*n-1:
        # 남은게 1개일때
        return False
    return True # 한개이상 존재


# main --------------------------------
dr = [0,1,0,-1] #우/하/좌/상
dc = [1,0,-1,0]
drr = [0,1,0,-1,1,1,-1,-1]
dcc =[1,0,-1,0,1,-1,-1,1]
attacker_history=[[0]*m for _ in range(n)]
for kk in range(k):
    attack_related = [[False] * m for _ in range(n)]
    attacker = attacker_choose()
    target_choose_attack(attacker)
    conti = resetting()
    if not conti: # 포탑이 하나만 남으면
        break

ans =0 # 최대 공격력 찾기
for i in range(n):
    for j in range(m):
        ans = max(grid[i][j], ans)
print(ans)

 

 

정답!