포탑 부수기 [삼성 기출]

1. 문제 접근 방법

- 문제의 정답은 맞추었다

- 보완할 부분은

(1) 효율성 부분

- path를 copy.deepcopy하는 식으로 접근했는데, 이 부분에서 효율성이 많이 깎였다

-> 그냥 path에다가 새로운 리스트 [[nx, ny]]를 + 하면 추가가 된다.

-> 이렇게 해야 한다

 

(2) 코드 간결화 부분

- towers라는 리스트를 만들어서 전역으로 관리했었는데, 

  이렇게 하니까 중간중간 정보가 바뀔때마다, 업데이트를 하는 것이 필요했다. 

-> 굳이 x, y, 공격력, 가장 최근 시간 정보를 리스트로 다 들고 있을 필요가 없다

-> x,y, 공격력은 board 저장되므로, board에 저장하고, 가장 최근 시간 정보는 times라는 2차원 board를 만들어서 저장한다.

-> 이렇게 하면 정보의 중복을 제거할 수 있고, 업데이트를 그때 그때 할 필요가 없으므로 효율적이다 

 

- 공격자와 피공격자를 나타내는 정보가 정확히 반대이다. 

  따라서, 이것을 메소드를 2개를 만들어서, 분리하는 것이 아니라, 

  하나를 만들어서 정리한 후에, 하나는 맨 앞에서, 다른 하나는 맨 끝에서 꺼내쓰면 된다. 

 

(3) 테스트 케이스 부분

- attack값을 리턴할 때는, 업데이트된 값을 리턴해야 한다

- bombAttack에 대해서는 공격자의 좌표는 해당되지 않아야 한다

-> 테스트 케이스로 잡은 것은 좋았으나, 문제를 좀 더 꼼꼼히 읽고 반영했으면 더 좋았을 것 같다. 

- 포탑이 한 개 남으면 바로 break한다는 점도 잘 반영해야 한다. 

 

 

2. 코드

from collections import deque 
import copy 

N, M, K = map(int, input().split())


board = [] 
times = [[0]*M for _ in range(N)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0] 

dx2 = [0, -1, -1, -1, 0, 1, 1, 1]
dy2 = [1, 1, 0, -1, -1, -1, 0, 1]


def isInside(x, y):
    if 0<=x and x<N and 0<=y and y<M:
        return True
    else:
        return False


for i in range(N):
    row = list(map(int, input().split()))
    board.append(row)
    
    
            

def printBoard():
    
    for i in range(N):
        for j in range(M):
            print(board[i][j], end=' ')
        print('', end='\n')
    print('', end='\n')
            
        
def choose(time):
    
    temp = [] 
    
    for i in range(N):
        for j in range(M):
            if board[i][j] >= 1:
                temp.append([i, j, board[i][j], times[i][j]])
    
    temp.sort(key=lambda x:[x[2], -x[3], -(x[0]+x[1]), -x[1]])
    
    attackTower = temp[0]
    attackedTower = temp[-1]
    
    x = attackTower[0]
    y = attackTower[1]
    
    board[x][y] += (M+N)
    times[x][y] = time 
    ## print("Attacker 선정")    
    ## printBoard()
    ## print(towers)
    
            
    return board[x][y], x,y, attackedTower[0], attackedTower[1] 
    
    
    

            


def razorAttack(sx, sy, ex, ey):
    
    visited = [[False]*M for _ in range(N)]
    
    path = [] 
    q = deque()
    q.append([sx, sy, path])
    visited[sx][sy] = True 
    
    
    while q:
        
        x, y, currPath = q.popleft()
        
        if x == ex and y == ey:
            return currPath 
            
        
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            
            if isInside(nx, ny):
                if visited[nx][ny] == False and board[nx][ny] >= 1:
                    visited[nx][ny] = True
                    ## nextPath = copy.deepcopy(currPath)
                    ## nextPath.append([nx, ny])
                    q.append([nx, ny, currPath+[[nx, ny]]])
            else:
                if nx == -1:
                    nx += N
                elif nx == N:
                    nx -= N
                    
                if ny == -1:
                    ny += M
                elif ny == M:
                    ny -= M 
                    
                
                if visited[nx][ny] == False and board[nx][ny] >= 1:
                    visited[nx][ny] = True
                    ## nextPath = copy.deepcopy(currPath)
                    ## nextPath.append([nx, ny])
                    q.append([nx, ny, currPath+[[nx,ny]]])            
        
        
    return None 
    
    
    
    
    
def bombAttack(attackerX, attackerY, sx, sy, attack):
    
    
    bombedTowers = [] 
    bombedTowers.append([sx, sy])
    
    board[sx][sy] -= attack

    
    ## print("bombAttack의 attackerX, attackerY")
    ## print(attackerX, attackerY)
        
    
    for i in range(8):
        nx = sx + dx2[i]
        ny = sy + dy2[i]
        
        if nx == attackerX and ny == attackerY:
            continue 
        
        if isInside(nx, ny):
            if board[nx][ny] >= 1:
                board[nx][ny] -= (attack // 2)
                bombedTowers.append([nx, ny])
                
            
        else:
            if nx == -1:
                nx += N
            elif nx == N:
                nx -= N
                    
            if ny == -1:
                ny += M
            elif ny == M:
                ny -= M
                
                
            if nx == attackerX and ny == attackerY:
                continue 
            
            
            if board[nx][ny] >= 1:
                board[nx][ny] -= (attack // 2)
                bombedTowers.append([nx, ny])
                
    
    
    return bombedTowers        
    
    
    


def razorDecrease(path, attack):
    
    ## print("attack은?")
    ## print(attack)
    
    pathLen = len(path)
    
    
    for i in range(pathLen):
        
        x = path[i][0]
        y = path[i][1] 
        
        if i == pathLen-1:
            board[x][y] -= attack
        else:
            board[x][y] -= (attack//2)
            
        
    



def breakTower():
    
    for i in range(N):
        for j in range(M):
            if board[i][j] <= 0:
                board[i][j] = 0 
                


def repairTower(attackerX, attackerY, attackedTowers):
    
    ## print("attackedTowers는?")
    ## print(attackedTowers)
    
    
    for i in range(N):
        for j in range(M):
            if i == attackerX and j == attackerY:
                continue 
            
            if board[i][j] >= 1 and [i, j] not in attackedTowers:
                ## print("i, j는 공격 받지 않음")
                ## print(i, j)
                board[i][j] += 1
                


def getStrongestTower():
    
    maxTower = 0
    
    for i in range(N):
        for j in range(M):
            maxTower = max(maxTower, board[i][j])



    return maxTower     
    


def getTowersCnt():
    
    cnt = 0 
    
    for i in range(N):
        for j in range(M):
            if board[i][j] >= 1:
                cnt += 1 
                
                
    return cnt 



time = 1 


while True:
    
    
    ## 700번
    attack, attackerX, attackerY, attackedX, attackedY = choose(time) 

    ## print(attackerX, attackerY, attack, attackedX, attackedY)
    
    
    razorPath = razorAttack(attackerX, attackerY, attackedX, attackedY)
    
    ## print("razorPath는?")
    ## print(razorPath)
    
    if razorPath != None:
        ## print(razorPath)
        razorDecrease(razorPath, attack)
        breakTower()
        
        ## print("Repair 이전")
        ## printBoard() 
        
        repairTower(attackerX, attackerY, razorPath)
        
    else:
        bombedTowers = bombAttack(attackerX, attackerY, attackedX, attackedY, attack)
        breakTower() 
        repairTower(attackerX, attackerY, bombedTowers)
    
    
    ## print(str(time) + "결과!")
    ## printBoard() 
    ## print(towers)
    
    cnt = getTowersCnt()
    
    
    time += 1 
    
    if cnt == 1 or time == K+1:
        break 


ans = getStrongestTower() 
print(ans)