[코드트리/삼성SW역량테스트] 포탑 부수기 (Python)

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

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

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:54:16

 

---

 

문제 설명 / 입력 및 출력

 

 

자세한 설명은 코드트리 사이트 링크를 참조해 주세요!

 

 

---

 

풀이

 

구현 + BFS. 구현에 30분, 디버깅에 20분 걸렸다. 이전의 1~2시간 넘는 디버깅 시간을 고려하면 조금 운이 좋았을지도.

 

레이저 공격은 우하좌상 순으로 우선도를 가지는 최소 경로를 따르므로, BFS를 이용해서 탐색하되 이전 노드를 같이 기록하도록 하자. 레이저가 방어자에게 도달한 순간 탐색을 종료하고, 방어자에게 도달하였는지 여부를 판단하자. 도달하였다면 백트래킹으로 경로상의 모든 타워들을 업데이트하면 되고, 그렇지 않다면 포탄 공격을 진행하자. 모든 노드가 연속적(즉 끝점에 도달하면 반대쪽으로 다다를 수 있음)이므로 mod를 이용하는 트릭을 사용하였다.

 

이외에도,

• 히스토리 기록 (공격자 선정 시 현재 시점 기록)
• 공격자 / 방어자 선정 시 우선순위 초기화 및 비교
• 공격자에게 핸디캡을 주는 시점과, 타워가 1 남았는지를 판단하는 시점(이 순서가 틀리면 공격자가 핸디캡을 얻고 탐색이 종료되는 등의 불상사가 생길 수 있다)

등을 고려해주면 되겠다.

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline

dr = [0, 1, 0, -1] 
dc = [1, 0, -1, 0]
ddr = [0, -1, -1, -1, 0, 1, 1, 1]
ddc = [-1, -1, 0, 1, 1, 1, 0, -1]

MAX = float('inf')

N, M, K = map(int, input().split())
towers = [list(map(int, input().split())) for _ in range(N)]
prev_attack = [[0]*M for _ in range(N)]
repaired = [[True]*M for _ in range(N)]

def find_attacker(t) :
    ba, br, bc, bt = MAX, -1, -1, -1
    cnt = 0
    for i in range(N) :
        for j in range(M) :
            if towers[i][j] == 0 :
                continue
            cnt += 1
            if (-ba, bt, br+bc, bc) < (-towers[i][j], prev_attack[i][j], i+j, j) :
                ba, br, bc, bt = towers[i][j], i, j, prev_attack[i][j]
    
    repaired[br][bc] = False
    prev_attack[br][bc] = t

    return (ba, br, bc, cnt)

def find_defender(ar, ac) :
    ba, br, bc, bt = 0, MAX, MAX, MAX
    for i in range(N) :
        for j in range(M) :
            if towers[i][j] == 0 or (ar, ac) == (i, j):
                continue
            if (-ba, bt, br+bc, bc) > (-towers[i][j], prev_attack[i][j], i+j, j) :
                ba, br, bc, bt = towers[i][j], i, j, prev_attack[i][j]
    
    return (br, bc)

def laser_attack(aa, ar, ac, br, bc) :
    visited = [[MAX]*M for _ in range(N)]
    visited[ar][ac] = 0
    parents = [[(i, j) for j in range(M)] for i in range(N)]
    q = deque([(0, ar, ac)])
    while q :
        dist, r, c = q.popleft()
        if (r, c) == (br, bc) :
            break
        for i in range(4) :
            _r, _c = (r + dr[i]) % N, (c + dc[i]) % M
            if towers[_r][_c] > 0 and visited[_r][_c] > dist + 1 :
                visited[_r][_c] = dist + 1
                parents[_r][_c] = (r, c)
                q.append((dist+1, _r, _c))

    if visited[br][bc] == MAX :
        return False
    
    towers[br][bc] = max(0, towers[br][bc] - aa)
    repaired[br][bc] = False
    pr, pc = parents[br][bc]
    while parents[pr][pc] != (pr, pc) :
        towers[pr][pc] = max(0, towers[pr][pc] - aa // 2)
        repaired[pr][pc] = False
        pr, pc = parents[pr][pc]
    return True

def bullet_attack(aa, ar, ac, br, bc) :
    towers[br][bc] = max(0, towers[br][bc] - aa)
    repaired[br][bc] = False
    for i in range(8) :
        r, c = (br + ddr[i]) % N, (bc + ddc[i]) % M
        if (r, c) == (ar, ac) :
            continue
        towers[r][c] = max(0, towers[r][c] - aa // 2)
        repaired[r][c] = False

def repair() :
    for i in range(N) :
        for j in range(M) :
            if towers[i][j] > 0 and repaired[i][j] :
                towers[i][j] += 1


for i in range(1, K+1) :
    repaired = [[True]*M for _ in range(N)]
    aa, ar, ac, cnt = find_attacker(i)
    if cnt == 1 :
        break
    aa += N + M
    towers[ar][ac] = aa
    
    br, bc = find_defender(ar, ac)
    is_attacked = laser_attack(aa, ar, ac, br, bc)
    if not is_attacked :
        bullet_attack(aa, ar, ac, br, bc)
    repair()

print(max(map(max, towers)))

풀이 완료!