[코드트리] - 포탑부수기

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20

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

 

문제종류

bfs, dx dy technique, simulation

풀이시간

설계 30분 구현 50분

풀이방법

1. 대상자 선정

문제에서 요구하는 공격 대상자와, 공격자를 구할때의 정렬 조건은 정반대입니다.

따라서 각 좌표의 공격, 최근 공격정보, 행 + 열, 열 정보를 모두 하나의 배열에 넣고

공격자, 대상자 = sorted(arr)[0], sorted(arr)[-1] 로 대상을 구하면됩니다.

공격자와 대상자가 같은 경우는 살아있는 포탑이 하나일경우 로직이 수행될 수 없으므로 불가능합니다.

 

2. 레이저 공격

공격자가 우 하 좌 상 순서의 움직임으로 대상에 도달할 수 있으면 레이저 공격을 할 수 있습니다.

대상자에서 공격자에 도달하는 bfs 를 수행후 

공격자에서 대상자로 가는 최단 경로를 저장합니다.

 

3. 포탄 공격

레이저 공격을 할 수 없을 경우, 즉 공격자의 상 하 좌 우 인접한 칸에 갈 수 없는 경우 수행합니다.

대상자의 8방향을 탐색하며 포탄 공격을 수행합니다. (공격자는 대상이 될 수 없는 것에 주의합니다.)

코드

from collections import deque

dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
bx, by = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
INF = 987654321

def transpose(nx, ny, n, m):
    nx = n - 1 if nx < 0 else nx % n
    ny = m - 1 if ny < 0 else ny % m
    return nx, ny


def main():
    n, m, k = map(int, input().split())
    arr = [list(map(int, input().split())) for i in range(n)]
    # 초기화 값
    EMPTY = (0, 0)
    # (공격력, 가장 최근 공격 저장)
    tower = [[EMPTY] * m for i in range(n)]
    for r in range(n):
        for c in range(m):
            tower[r][c] = (arr[r][c], 0)
    for turn in range(1, k + 1):
        # 살아있는 포탑이 1개면 종료
        live_cnt = 0
        for x in range(n):
            for y in range(m):
                if tower[x][y][0] > 0:
                    live_cnt += 1
        if live_cnt == 1:
            break
        attack_tmp = []
        for x in range(n):
            for y in range(m):
                # 이미 부서진 곳 후보에 넣지 않음
                if tower[x][y][0] != 0:
                    attack_tmp.append((*tower[x][y], x + y, y))

        # 영향 받은 좌표 저장
        hist = set()
        # 공격자 선정
        attacker = sorted(attack_tmp, key=lambda att: (att[0], -att[1], -att[2], -att[3]))[0]
        # 대상자 선정
        defender = sorted(attack_tmp, key=lambda att: (att[0], -att[1], -att[2], -att[3]))[-1]
        ax, ay = attacker[2] - attacker[3], attacker[3]
        hist.add((ax, ay))
        dfx, dfy = defender[2] - defender[3], defender[3]
        # 공격자 공격력 증가
        tower[ax][ay] = (tower[ax][ay][0] + n + m, turn)
        # 레이저 공격 판단
        rtmp = [[INF] * m for _ in range(n)]

        # bfs 수행 공격 대상 => 공격자 벽 통과 불가 => 한번 갔던 곳 더가기 불가
        q = deque([])
        q.append((dfx, dfy, 0))
        while len(q):
            fx, fy, fc = q.popleft()
            # 방문한곳이면 못감
            if rtmp[fx][fy] != INF:
                continue
            rtmp[fx][fy] = fc
            for ddx, ddy in zip(dx, dy):
                nx, ny = fx + ddx, fy + ddy
                nx, ny = transpose(nx, ny, n, m)
                if rtmp[nx][ny] != INF or tower[nx][ny][0] == 0:
                    continue
                q.append((nx, ny, fc + 1))

        min_dist = INF
        for ddx, ddy in zip(dx, dy):
            nx, ny = ax + ddx, ay + ddy
            nx, ny = transpose(nx, ny, n, m)

            min_dist = min(min_dist, rtmp[nx][ny])

        # 레이저 공격 수행
        if min_dist != INF:
            rpath = []
            cx, cy = ax, ay
            for rp in range(min_dist + 1):
                cmd = INF
                for ddx, ddy in zip(dx, dy):
                    nx, ny = cx + ddx, cy + ddy
                    nx, ny = transpose(nx, ny, n, m)
                    cmd = min(cmd, rtmp[nx][ny])
                # 우 하 좌 상으로 탐색하며
                for ddx, ddy in zip(dx, dy):
                    nx, ny = cx + ddx, cy + ddy
                    nx, ny = transpose(nx, ny, n, m)

                    if rtmp[nx][ny] == cmd:
                        rpath.append((nx, ny))
                        cx, cy = nx, ny
                        break

            # 레이저 공격 수행 (영향 범위에 추가)
            dam = tower[ax][ay][0]
            for ri, (rx, ry) in enumerate(rpath):
                t_dam = dam // 2
                if ri == len(rpath) - 1:
                    t_dam = dam
                tower[rx][ry] = (max(0, tower[rx][ry][0] - t_dam), tower[rx][ry][1])
                hist.add((rx, ry))
        # 포탄 공격 수행
        else:
            dam = tower[ax][ay][0]
            # 타켓 즉시 공격후 추가
            tower[dfx][dfy] = (max(0, tower[dfx][dfy][0] - dam), tower[dfx][dfy][1])
            hist.add((dfx, dfy))
            for bbx, bby in zip(bx, by):
                nx, ny = dfx + bbx, dfy + bby
                nx, ny = transpose(nx, ny, n, m)
                # 이미 부서진 곳이 아니고, 공격자가 아닐경우
                if tower[nx][ny][0] != 0 and (nx, ny) != (ax, ay):
                    tower[nx][ny] = (max(0, tower[nx][ny][0] - dam // 2), tower[nx][ny][1])
                    hist.add((nx, ny))
        # 포탑 정비
        for x in range(n):
            for y in range(m):
                if tower[x][y][0] != 0 and (x, y) not in hist:
                    tower[x][y] = (tower[x][y][0] + 1, tower[x][y][1])
    # turn 끝난이후
    ans = 0
    for r in range(n):
        for c in range(m):
            ans = max(ans, tower[r][c][0])
    print(ans)
main()