2023상_포탑 부수기 (2024/03/30 업데이트)

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description

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

해설

1. 초기 설정
   1. 공격시점, 공격관여 맵을 만들고, 관련된 함수 실행 시 지속 업데이트한다.
   2. 공격자, 공격대상의 위치를 따로 선정한다.
   3. 탐색 방향은 우,하,좌,상 순서로 한다. 이를 통해, 레이저 공격 시 만약 경로의 길이가 똑같은 최단 경로가 2개 이상이라면, 우/하/좌/상의 우선순위대로 먼저 움직인 경로가 선택된다.
   4. 8가지 대각선 탐색 방향은 따로 설정한다.
2. 전체 프로세스
   1. 라운드는 1부터 K까지 진행한다.
      1. 공격자 선정
      2. 공격대상 선정
      3. 공격 시도
         1. 레이저
         2. 포탄
      4. 포탑 부서짐 - 공격력 0 이하인 포탑은 0으로 설정
      5. 포탑 수 확인 - 부서지지 않은 포탑 1개만 남아있을 경우 중지
      6. 포탑 정비 - 공격력 1이상인 포탑의 공격력 +1
      7. 공격관여 맵 초기화
3. 개별 함수 설명
   1. 공격자 선정
      1. 맵을 전체 탐색하며, 공격력 0인 대상 제외하고 [공격력, 공격시점, 행+열, 열, 행] 을 arr 배열에 넣는다.
      2. 배열을 공격력 오름차순, 공격시점/행+열/열 내림차순으로 정렬한다.
      3. 맨 첫 번째 요소가 공격자다.
      4. 공격자의 공격력을 n+m만큼 증가시키고
      5. 공격관여와 공격시점을 업데이트한다
   2. 공격대상 선정
      1. 맵을 전체 탐색하며, 공격력 0인 대상과 공격자 제외하고 [공격력, 공격시점, 행+열, 열, 행] 을 arr 배열에 넣는다
      2. 배열을 공격력 내림차순, 공격시점/행+열/열 오름차순으로 정렬한다.
      3. 맨 첫 번째 요소가 공격대상이다.
      4. 공격관여를 업데이트한다
4. 공격 시도
   1. BFS 탐색으로 공격자~공격대상 최단 루트를 찾는다.
      1. 공격력 0인 부서진 포탑을 제외하고 맵을 일반적인 BFS 로 탐색하되, 아래 사항을 주의한다.
         
         1. 만약 맵 범위를 벗어난 곳을 탐색할 경우, 격자 반대편으로 점프한다.(outBound)
         2. parent 딕셔너리를 사용하여 최단 루트를 저장한다. parent 의 key 에는 다음 탐색할 칸, value 에는 현재 탐색 중인 칸이 튜플 형식으로 저장된다.
         3. 만약 탐색 도중 공격대상이 위치한 칸을 찾지 못할 경우 중지하고, 최단 경로가 존재하지 않음을 반환한다.
      2. 최단 루트를 route 배열에 담아 공격자~공격대상 순으로 정렬하여 반환한다.
   2. 최단 루트가 존재하면 레이저 공격
      1. 공격대상의 공격력을 공격자의 공격력만큼 감소시킨다.
      2. 최단 루트에서 공격자, 공격대상을 제외한다.
      3. 공격 대상 제외한 경로에 있는 포탑들 공격력 절반만큼 피해, 공격관여 업데이트 한다.
   3. 최단 루트가 존재하지 않으면 포탄 공격
      1. 공격대상의 공격력을 공격자의 공격력만큼 감소시킨다.
      2. 공격대상 주위 8개 공격 - 공격력 절반만큼(공격자 해당X), 공격관여 업데이트 한다.
         1. 이때, 초기 설정했던 8가지 대각선 탐색 방향을 사용한다.
         2. 만약 맵 범위를 벗어난 곳을 탐색할 경우, 격자 반대편으로 점프한다.(outBound)

소스코드

from collections import deque

n,m,K=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)] # 공격력
b=[[0]*m for _ in range(n)] # 공격시점
c=[[False]*m for _ in range(n)] # 공격관여

ax,ay=-1,-1 # 공격자
tx,ty=-1,-1 # 공격대상

#  우,하,좌,상
dx=[0,1,0,-1]
dy=[1,0,-1,0]

# 대각선
dx1=[-1,-1,-1,0,0,1,1,1]
dy1=[-1,0,1,-1,1,-1,0,1]

def selectAttacker(round):
    global ax,ay,a,b,c

    # 공격자 선정
    arr=[]
    for x in range(n):
        for y in range(m):
            if a[x][y]==0:continue
            arr.append([a[x][y],b[x][y],x+y,y,x])
    arr.sort(key=lambda x:(x[0],-x[1],-x[2],-x[3]))
    ax,ay=arr[0][-1],arr[0][-2]

    # 공격력 증가
    a[ax][ay]+=n+m
    # 공격관여와 공격시점 업데이트
    c[ax][ay]=True
    b[ax][ay]=round

def selectAttacked(round):
    global tx,ty,a,b,c

    # 공격대상 선정
    arr=[]
    for x in range(n):
        for y in range(m):
            if a[x][y]==0:continue
            if (x,y)==(ax,ay): continue
            arr.append([a[x][y],b[x][y],x+y,y,x])
    arr.sort(key=lambda x:(-x[0],x[1],x[2],x[3]))
    tx,ty=arr[0][-1],arr[0][-2]

    # 공격관여 업데이트
    c[tx][ty] = True


def inBoard(nx,ny):
    if 0<=nx<n and 0<=ny<m:
        return True
    return False

def outBoard(nx,ny):
    if nx==-1:
        nx=n-1
    if nx==n:
        nx=0
    if ny==-1:
        ny=m-1
    if ny==m:
        ny=0
    return [nx,ny]

def bfs():

    # 공격자 - 공격대상까지의 최단 루트 탐색
    q=deque()
    q.append((ax,ay))
    visit=[[False]*m for _ in range(n)]
    visit[ax][ay]=True
    parent=dict()
    ok=False # 최단 루트 존재 여부

    while q:
        x,y=q.popleft()
        for k in range(4):
            nx,ny=x+dx[k],y+dy[k]
            # 보드 범위 벗어날 경우 격자 반대편으로 점프
            if not inBoard(nx,ny):
                nx,ny=outBoard(nx,ny)
            if a[nx][ny]>0 and visit[nx][ny]==False:
                visit[nx][ny]=True
                q.append((nx,ny))
                parent[(nx,ny)]=(x,y)
                # 공격 대상 찾았으면 최단 경로 존재
                if (nx,ny)==(tx,ty):
                    ok=True
    # 최단 경로 존재하지 않으면 False 반환
    if ok==False:
        return [None,False]

    start=(ax,ay)
    end=(tx,ty)
    current=end
    route=[current]
    while current!=start:
        current=parent[current]
        route.append(current)
    route.reverse() # 최단 루트

    return [route,True]

def laser(route):
    global a,c

    # 공격대상 공격력 감소
    a[tx][ty]-=a[ax][ay]
    # 최단 루트에서 공격자, 공격대상 제외
    route=route[1:-1]
    # 공격 대상 제외한 경로에 있는 포탑들 공격력 절반만큼 피해, 공격관여 업데이트
    for x,y in route:
        a[x][y]-=a[ax][ay]//2
        c[x][y]=True

def canon():
    global a,c

    # 공격대상 공격력 감소
    a[tx][ty]-=a[ax][ay]
    # 공격대상 주위 8개 공격 - 공격력 절반만큼(공격자 해당X), 공격관여 업데이트
    x,y=tx,ty
    for k in range(8):
        nx,ny=x+dx1[k],y+dy1[k]
        if not inBoard(nx, ny):
            nx, ny = outBoard(nx, ny)
        if a[nx][ny] > 0 and (nx,ny)!=(ax,ay):
            a[nx][ny]-=a[ax][ay]//2
            c[nx][ny]=True

def attack():
    route,ok = bfs()
    # 최단 경로 존재하면 레이저 공격
    if ok:
        laser(route)
    # 최단 경로 존재하지 않으면 포탄 공격
    else:
        canon()

def zeroCheck():
    global a

    for x in range(n):
        for y in range(m):
            if a[x][y]<=0:
                a[x][y]=0

def stop():
    cnt=0
    for x in range(n):
        for y in range(m):
            if a[x][y]>0:
                cnt+=1
    if cnt==1:
        return True
    return False

def fix():
    global a

    for x in range(n):
        for y in range(m):
            if a[x][y]==0 or c[x][y]:continue
            a[x][y]+=1

for round in range(1,K+1):
    # 공격자 선정
    selectAttacker(round)
    # 공격대상 선정
    selectAttacked(round)
    # 공격 시도
    attack()
    # 포탑 부서짐
    zeroCheck()
    # 포탑 수 확인 - 부서지지 않은 포탑 1개만 남아있을 경우 중지
    ok=stop()
    if ok:
        break
    # 포탑 정비
    fix()
    # 공격 관여 초기화
    c=[[False]*m for _ in range(n)] # 공격관여

max_val=-1
for x in range(n):
    for y in range(m):
        max_val=max(max_val,a[x][y])

print(max_val)