코드트리 포탑 부수기 | python | 우선 순위, bfs 최단경로 좌표 추적

Konseo·2023년 10월 10일
0

코테풀이

목록 보기
42/59

문제

링크

풀이

구현 순서 정리 (문제 함수별로 정리)

  1. 공격자 선정
    • 부서지지 않은 포탑 중 가장 약한 포탑이 공격자로 선정
    • 가장 약한 포탑 선정 기준 (우선순위 순)
      • 공격력이 가장 낮은 포탑
      • 가장 최근에 공격한 포탑
      • (행+열)의 합이 큰 포탑
      • 열 값이 가장 큰 포탑
    • 공격자에겐 n+m 만큼 공격력 부여
  2. 공격대상 선정
    • 부서지지 않은 포탑 중 가장 강한 포탑이 공격자로 선정
    • 가장 강한 포탑 선정 기준 (우선순위 순)
      • 공격력이 가장 높은 포탑
      • 공격한 지 가장 오래된 포탑
      • (행+열)의 합이 작은 포탑
      • 열 값이 가장 작은 포탑
  3. 공격
    • 공격은 레이저공격과 포탑공격 두 가지가 존재
      • 모두 다 하는 건 아니고, 레이저 공격을 할 수 없는 경우에만 포탑 공격 진행
    • 레이저 공격
      • 최단 경로로 공격한다고 하였으니 -> bfs 진행
      • 최단 경로가 여러개인 경우 -> 우/하/좌/상 순서로 우선순위를 가짐
      • !최종 선택된 최단 경로에 있는 포탑들도 공격 받음! 주의
    • 포탄 공격
      • 공격 대상 뿐 아니라 인접한 8칸에 존재하는 포탑에도 공격 받음
      • 얼만큼 피해를 입는지는 레이저와 동일함
        • 공격 대상 : 공격자의 공격력 만큼 피해를 입음
        • 경로에 있던 포탑(레이저) or 인접 포탑(포탄) : 공격자의 공격력//2 만큼 피해를 입음
  4. 포탑 부서짐
    • 공격을 받아 0 이하가 된 포탑은 없어짐
  5. 포탑 재정비
    • (이번 사이클에서) 공격자도 아니고, 공격도 받지 않은 공격과 무관했던 포탄은 공격력 +1 증가
  6. 1~5까지가 한 사이클임. 포탑이 1개가 되면 그 즉시 중지(break)
  7. 최종적으로 남아있는 포탑 중 가장 강한 포탑의 공격력을 출력하면 됨

사용한 배열

포탑 정보 board (N x M)
공격 시점 체크 배열 history (N x M) -> 공격 포탑에게 현재 시간 기록
공격 관련 여부 체크 배열 attack (N x M) -> turn 마다 초기화

막혔던 부분

  1. 가장 최근에 공격한 포탑을 어떻게 저장하는가?
    • history 전역 배열을 사용해 공격하는 포탑의 현재 시간을 기록해 둠
    • 즉, history 값이 클수록 최근 공격한 포탑, 작을수록 공격한 지 오래된 포탑
  2. 공격자, 공격대상 선정할 때 (행+열)과 같은 우선순위 로직 어떻게 처리할까?
    • 그냥 우선 순위 순서대로 조건을 잘 걸어두면 됨
    • get_attacker()
      def get_attacker():
      global attacker
      power = 5001
      global attacker
      ay,ax = attacker
      for y in range(N):
        for x in range(M):
            if board[y][x] == 0:  continue
            if board[y][x] < power: # 우선순위 1 : 공격력이 가장 낮은 포탑
                power = board[y][x]
                ay,ax = y,x
            elif board[y][x] == power: 
                if history[y][x] > history[ay][ax]: # 우선순위 2 : 가장 최근에 공격한 포탑
                    ay,ax=y,x
                elif history[y][x] == history[ay][ax]:
                    if y+x > ay+ax: # 우선 순위 3 : (행+열)의 합이 큰 포탑
                       ay,ax=y,x
                    elif x + y == ax + ay: # 우선 순위 4: 열 값이 가장 큰 포탑
                        if x > ax:
                            ay,ax=y,x
      attacker=(ay,ax)
    • 원래는 가능한 후보들을 candidate 라는 배열에 저장해두고 lambda로 정렬 조건 걸어서 진행했는데 이 방식은 부가적으로 처리해야하는 코드가 있어서 실수가능성이 더 큰 것 같음. 따라서 위와 같은 직관적인 방식을 잘 사용하는 게 나을 듯
      • 맨 처음 작성한 코드
      def get_attacker():
      global board,history,attacker
      MIN=5001
      candidate=[]
      for i in range(len(board)):
          for j in range(len(board)):
              if board[i][j]!=0:
                  if MIN>board[i][j]:
                      candidate=[]
                      candidate.append((i,j,history[i][j]))
                      MIN=board[i][j]
                  elif MIN==board[i][j]:
                      candidate.append((i,j,history[i][j]))
      if len(candidate) >1:
          candidate.sort(key=lambda x:(-x[2],-(x[0]+x[1]),-x[0]))
      ay,ax,_=candidate[0]
      attacker=(ay,ax)
  3. 막힌 방향 진행 시 반대편으로 나오는건 어떻게 구현하는가?
    • 알고보니 낚시왕이나 토끼와 경주같이 벽에서 부딪혀서 방향이 바뀌는게 아니라 그냥 n행(열)과 1행(열)이 연결되어 있다고 생각하면 되므로 별도의 처리가 필요 없었음. 패스
  4. 최단 경로니까 bfs인 건 알겠으나 움직이는 것에도 우선순위가 있다면 어떻게 처리해야하는가?
    • 그냥 우선순위 순서대로 방향을 돌리면 자연히 우선순위에 따라 최단 경로를 찾을 수 있게 됨
  5. 선택된 경로에 있는 포탑도 공격하려면 경로들의 좌표들도 담고 있어야 해. 어떻게 표현하지?
    • 처음엔 visited 배열에 True 값대신 직전 좌표 값을 넣어두려 했는데 방문여부와 좌표 기록을 하나의 배열에서 해결하려니까 너무 복잡해졌음
    • 관심사 분리해서 visited는 단순히 방문 여부만 판단하고, 큐에 좌표와 더불어 경로 기록을 위한 배열을 추가로 둠.
  6. NxM 배열 주의 🥵
    • 이건 NxN 배열이라고 혼자 생각하고 디버깅 N시간하고 너무나도 현타와서 적음. 예시가 모두 정사각형이라고 NxN 배열이라고 착각하지 말자. 실제 시험장에선 실수하지 말자. 정확하게 읽고 푸는 게 관건

전체 코드

from collections import deque
import copy
N,M,k=map(int,input().split())
d=[(0,1),(1,0),(0,-1),(-1,0)]
d_8=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

board=[]
for _ in range(N):
    board.append(list(map(int,input().split())))
history=[[0]*M for _ in range(N)] # 최근 공격 시간 기록
t=1

attacker=(-1,-1)
target=(-1,-1)

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


def get_attacker():
    global attacker
    power = 5001
    global attacker
    ay,ax = attacker
    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:  continue
            if board[y][x] < power:
                power = board[y][x]
                ay,ax = y,x
            elif board[y][x] == power: # 여기서부터는 우선순위 비교 들어감
                if history[y][x] > history[ay][ax]:
                    ay,ax=y,x
                elif history[y][x] == history[ay][ax]:
                    if y+x > ay+ax:
                       ay,ax=y,x
                    elif x + y == ax + ay:
                        if x > ax:
                            ay,ax=y,x
    attacker=(ay,ax)

def get_attack_target():
    global history

    power = -1
    global target
    ty,tx=target
    for y in range(N):
        for x in range(M):
            if board[y][x] == 0:  continue
            if x == ax and y == ay: continue
            if board[y][x] > power:
                power = board[y][x]
                ty,tx=y,x
            elif board[y][x] == power:
                if history[y][x] < history[ty][tx]:
                    ty,tx=y,x
                elif history[y][x] == history[ty][tx]:
                    if x + y < tx + ty:
                        ty,tx=y,x
                    elif x + y == tx + ty:
                        if x<tx:
                            ty,tx=y,x
    target=(ty,tx)


def laser_attack():
    global attacker,target
    ax,ay= attacker
    tx,ty=target
    '''
    경로 체크하기 위해 q 에 리스트 요소 정의
    '''
    q = deque()
    q.append((ax, ay, []))  # x, y, route
    visited = [[False] * M for _ in range(N)]
    visited[ax][ay] = True

    while q:
        x, y, route = q.popleft()
        for dx,dy in d:

            nx = (x + dx) % N
            ny = (y + dy) % M
            if visited[nx][ny]: continue
            if board[nx][ny] == 0: continue

            # 타겟에 도달한 경우
            if nx == tx and ny == ty:
                board[nx][ny] -= point
                for rx, ry in route:  # 경로 추적
                    board[rx][ry] -= half_point
                    attack[rx][ry] = True
                return True

            # 경로 체크
            tmp_route = route[:]
            tmp_route.append((nx, ny))
            visited[nx][ny] = True
            q.append((nx, ny, tmp_route))

    # 타겟이 도달하지 못하는 경우
    return False


def shell_attack():
    global attacker,target
    ax,ay=attacker
    tx,ty=target
    board[tx][ty] -= point
    for dx,dy in d_8:
        nx = (tx + dx) % N
        ny = (ty + dy) % M
        if nx == ax and ny == ay:   continue
        board[nx][ny] -= half_point
        attack[nx][ny] = True


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

def max_check():
    return max([max(line) for line in board])
    
def maintain_top():
    turret = []
    turret_cnt = 0
    for x in range(N):
        for y in range(M):
            if board[x][y] == 0:  continue
            turret_cnt += 1
            if attack[x][y]:    continue
            turret.append((x, y))

    if turret_cnt == 1:
        print(max_check())
        exit(0)
    for x, y in turret:
        board[x][y] += 1


for i in range(k):
    attack = [[0] * M for _ in range(N)]

    # print_board()
    get_attacker()
    ay,ax=attacker
    attack[ay][ax]=1
    history[ay][ax]=t
    t += 1
    board[ay][ax]+=(N+M)
    # print('공격자',attacker)

    get_attack_target()
    ty, tx = target
    attack[ty][tx] = 1
    # print_board()
    # print('공격대상',target)
    point = board[ay][ax]
    half_point = point // 2
    if not laser_attack():
        shell_attack()
    # print_board()
    remove_top()
    # print_board()
    maintain_top()
    # print_board()
    # print('1 turn 완료')

print(max_check())

결론

조금 더 명확하고 자세히 읽기. 설계하고 함수 고민하는 데 충분한 시간을 쏟자. 문장 그대로 구현하려고 노력하기. 삼성 문제에서 함수는 쪼개면 쪼갤수록 좋다.

profile
둔한 붓이 총명함을 이긴다

0개의 댓글