[삼성 기출] 포탑 부수기

 

코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리

 

 

Key Idea

최단 경로 탐색만 정확히 구현할 수 있다면, 전체 구현 자체는 비교적 정직한 시뮬레이션 문제라고 생각한다.
문제를 해결하는 과정에서는 먼저 시스템의 Invariant를 정의한 뒤, 이를 기반으로 Controller → Service → Repository 순으로 레이어를 분리하며 설계와 구현을 진행하였다. 각 레이어는 자신의 추상화 수준에 맞는 책임만 가지도록 구성하였으며, 현재 레이어에서 다루기 적절하지 않은 정보나 로직이 필요한 경우에는 하위 컴포넌트에 책임을 위임하여 추상화 일관성을 유지하고자 하였다.
 
Invariant 설계를 기반으로 각 컴포넌트의 역할과 세부 구현을 설명하겠다.
 

Invariant

board[x][y]는 [POWER, LAST_ATTACK_TIME] 정보를 저장하며, eager update 방식을 통해 항상 최신 상태를 유지하도록 설계하였다.
또한 모든 좌표는 0-based indexing으로 통일하여 관리하였다.
부서진 포탑 여부를 별도의 자료구조로 관리하지 않고, POWER 값이 0 이하인 경우를 부서진 포탑으로 간주하도록 Invariant를 정의하였다. 이를 통해 추가 메모리 사용을 줄이고 상태 관리 복잡도를 낮추고자 하였다.
특히 부서진 포탑은 다시 복구되지 않는 absorbing state로 간주하였기 때문에, 이후 추가 공격으로 인해 POWER 값이 더 감소하더라도 별도의 예외 처리를 수행하지 않도록 설계하였다.
 
 

Architecture

UML

 

 

 

Implementation - Adapter

입력으로 주어지는 board 배열은 각 칸마다 포탑의 공격력 정보만을 포함하고 있다.
하지만 문제를 해결하기 위해서는 “마지막 공격 시각” 또한 함께 관리할 필요가 있었기 때문에, 이를 저장할 수 있도록 내부 표현을 변환하는 Adapter를 적용하였다.
 
구체적으로는 입력 단계에서 기존의 2차원 배열을

board[x][y] = [POWER, LAST_ATTACK_TIME]

형태의 3차원 배열 구조로 변환하여 저장하였다.
 
이를 통해 이후 로직에서는 공격력과 마지막 공격 시각을 하나의 상태로 함께 관리할 수 있었으며, 별도의 자료구조를 추가로 관리하지 않고도 상태 일관성을 유지할 수 있도록 하였다.
 
 

class Adaptor():
    def read_parameter(self):
        N,M,K=map(int,input().split())
        self.N=N
        self.M=M
        self.K=K
        return N,M,K
    def read_board(self):
        raw_board_data=[list(map(int,input().split())) for _ in range(self.N)]
        board=[[[0,0] for _ in range(self.M)] for _ in range(self.N)]
        for x in range(self.N):
            for y in range(self.M):
                board[x][y][0]=raw_board_data[x][y]
        return board

 

 

Implementation - Controller

레이저 공격은 실패할 수 있으므로, 레이저 공격 성공 여부를 확인하기 위한 bool 반환값을 추가로 반환하도록 설계하였다.
또한 전체 터렛은 {공격자, 수비자, 희생자}로 나눌 수 있고 이를 집합 연산으로 처리하여 공격과 관련 없는 터렛을 선정하였다.
그리고 턴 종료 이전에 문제에서 제시된 바와 같이 부서지지 않는 터렛이 1개만 남을 경우 시뮬레이션이 종료되도록 하였다.
이 조건이 있기 때문에 공격자, 수비자를 찾는 로직은 항상 1개의 값을 반환하는 것이 보장되며, 추가적으로 다음과 같은 고민이 필요했다.
 
"과연 게임판에 살아있는 포탑이 0개가 되는 상황은 존재하지 않을까?"
이를 위해 아래 명제 P를 증명해야 한다.
 
명제 P: 모든 턴 k에 대해, 게임판에 살아있는 포탑이 0개인 상황은 존재하지 않는다.
Base: 1번째 턴 시작 시에는 문제 조건상 부서지지 않은 포탑이 2개 이상 존재하므로 P는 성립한다.
Induction: k번째 턴 시작 시 P가 성립한다고 가정하자. 공격이 수행될 때 공격자는 피해를 입지 않으므로, 해당 턴이 끝난 뒤에도 살아있는 포탑은 최소 1개 이상 존재한다. 따라서 살아있는 포탑이 0개가 되는 상황은 발생하지 않는다.
이때 k번째 턴 종료 후 살아있는 포탑이 정확히 1개라면 Controller의 종료 조건에 의해 시뮬레이션이 종료된다.
따라서 k+1번째 턴이 시작되었다면, 살아있는 포탑 수는 0개도 아니고 1개도 아니므로 최소 2개 이상이다. P 성립.
 
따라서 각 턴이 시작되는 시점에는 항상 공격자와 수비자를 선택할 수 있으며, 살아있는 포탑이 0개가 되는 별도의 엣지케이스는 고려하지 않아도 된다는 확신을 가지고 코드를 작성하였다.
 

class Controller():
    def __init__(self,K,service):
        self.K=K
        self.service=service
    def run(self):
        for turn in range(1,self.K+1):
            attacker=self.service.choose_attacker(turn)
            defender=self.service.choose_defender(attacker)
            is_success,victims=self.service.attack_laser(attacker,defender)
            if not is_success:
                victims=self.service.attack_cannon(attacker,defender)
            related_turrets={attacker,defender}|victims
            unrelated_turrets=self.service.get_all_undestroyed_turret()-related_turrets
            self.service.repair_turrets(unrelated_turrets)
            if self.service.count_unbroken_turret()==1:
                break
        print(self.service.get_strongest_turret_power())

 
 

 

Implementation - Service

 
Service 레이어에서는 직접 메모리에 접근하지 않고, 모든 상태 조회 및 수정 연산을 Repository에 위임하였다. 이를 통해 상태 관리 책임을 Repository로 일원화하고, Service는 문제에서 요구하는 비즈니스 로직만 담당하도록 설계하였다.

class Service():
    def __init__(self,N,M,repository):
        self.repository=repository
        self.handicap=N+M
    def choose_attacker(self,turn:int)->Position:
        ''' choose attacker, record last attack timing and give handicap '''
        attacker:Position=self.repository.get_weakest_turret()
        self.repository.update_last_attack(attacker,turn)
        self.repository.update_power(attacker,self.handicap)
        return attacker
    def choose_defender(self,attacker:Position)->Position:
        ''' choose defender excepting attacker itself '''
        return self.repository.get_strongest_turret(attacker)
    def attack_laser(self,attacker:Position,defender:Position)->tuple[bool,set[Position]]:
        is_exist,affected_turrets=self.repository.get_shortest_path(attacker,defender)
        if not is_exist:
            return False,set()
        damage:int=self.repository.get_power(attacker)
        splash_damage:int=damage//2
        self.repository.update_power(defender,-damage)
        for turret in affected_turrets:
            self.repository.update_power(turret,-splash_damage)
        return True,affected_turrets
    def attack_cannon(self,attacker:Position,defender:Position)->set[Position]:
        neighbor:set[Position]=self.repository.get_neighbor(defender) # this return except defender
        affected_turrets=neighbor-{attacker}
        damage:int=self.repository.get_power(attacker)
        splash_damage:int=damage//2
        self.repository.update_power(defender,-damage)
        for turret in affected_turrets:
            self.repository.update_power(turret,-splash_damage)
        return affected_turrets
    def get_all_undestroyed_turret(self)->set[Position]:
        return self.repository.get_all_undestroyed_turret()
    def repair_turrets(self,turrets:set[Position])->None:
        for turret in turrets:
            self.repository.update_power(turret,1)
    def count_unbroken_turret(self)->int:
        return self.repository.count_unbroken_turret()
    def get_strongest_turret_power(self)->int:
        return self.repository.get_strongest_turret_power()

 

 

Implementation - Repository

 
상태 board에 직접 접근하여 필요한 정보를 상위 레이어에 전달하는 역할을 수행한다.
가장 강한, 약한 터렛을 선정하는 과정에서는 튜플 우선순위를 이용한 트릭을 사용하여 가독성을 높였다.
또한 시작점에서 종점까지 최단거리를 구하는 로직은 BFS로 탐색 순서대로 탐색하다 첫번째로 발견하는 경로가 경로를 우선순위 대로 만드므로 가장 좋은 경로임을 보장할 수 있었다.
따라서 중간 경로는 이전 노드의 위치를 기입해두고, 최단 거리가 구해졌다면 종점에서 시작점으로 거꾸로 추적하여 전체 경로를 구성하였다.
 

class Repository():
    def __init__(self,N,M,board):
        self.N=N
        self.M=M
        self.board=board
    def get_neighbor(self,entity:Position)->set[Position]:
        ''' returns neighbor except entitiy itself '''
        neighbor=set()
        cx,cy=entity
        for dx in [-1,0,1]:
            for dy in [-1,0,1]:
                if dx==0 and dy==0:
                    continue
                nx,ny=(cx+dx)%self.N,(cy+dy)%self.M
                neighbor.add((nx,ny))
        return neighbor
    def is_alive(self,x,y)->bool:
        return self.board[x][y][Turret.POWER]>0
    def get_weakest_turret(self)->Position:
        # ( power, -last_attack, -(x+y), -y, x, y )
        best=INF,INF,INF,INF,INF,INF
        for x in range(self.N):
            for y in range(self.M):
                if not self.is_alive(x,y):
                    continue
                cur=self.board[x][y][Turret.POWER],-self.board[x][y][Turret.LAST_ATTACK],-(x+y),-y,x,y
                best=min(best,cur)
        return best[-2:]
    def update_last_attack(self,entity:Position,turn:int)->None:
        cx,cy=entity
        self.board[cx][cy][Turret.LAST_ATTACK]=turn
    def update_power(self,entity:Position,amount:int)->None:
        cx,cy=entity
        self.board[cx][cy][Turret.POWER]+=amount
    def get_strongest_turret(self,entity:Position)->Position:
        # ( power, -last_attack, -(x+y), -y, x, y )
        best=-INF,-INF,-INF,-INF,-INF,-INF
        for x in range(self.N):
            for y in range(self.M):
                if (x,y)==entity:
                    continue
                if not self.is_alive(x,y):
                    continue
                cur=self.board[x][y][Turret.POWER],-self.board[x][y][Turret.LAST_ATTACK],-(x+y),-y,x,y
                best=max(best,cur)
        return best[-2:]
    def get_shortest_path(self,start:Position,end:Position)->tuple[bool,set[Position]]:
        # BFS
        queue=deque()
        parent=dict()
        queue.append(start)
        parent[start]=None
        while queue:
            cx,cy=queue.popleft()
            if (cx,cy)==end:
                path=set()
                cur=parent[end]
                while cur!=start:
                    path.add(cur)
                    cur=parent[cur]
                return True,path
            for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                nx,ny=(cx+dx)%self.N,(cy+dy)%self.M
                if (nx,ny) in parent:
                    continue
                if not self.is_alive(nx,ny):
                    continue
                queue.append((nx,ny))
                parent[(nx,ny)]=(cx,cy)
        return False,set()
    def get_power(self,entity:Position)->int:
        cx,cy=entity
        return self.board[cx][cy][Turret.POWER]
    def get_all_undestroyed_turret(self)->set[Position]:
        undestroyed_set=set()
        for x in range(self.N):
            for y in range(self.M):
                if self.is_alive(x,y):
                    undestroyed_set.add((x,y))
        return undestroyed_set
    def count_unbroken_turret(self)->int:
        count=0
        for x in range(self.N):
            for y in range(self.M):
                if self.is_alive(x,y):
                    count+=1
        return count
    def get_strongest_turret_power(self)->int:
        best=-INF
        for x in range(self.N):
            for y in range(self.M):
                cur=self.board[x][y][Turret.POWER]
                best=max(best,cur)
        return best

 
 

 

CODE

 
전체 시간 복잡도는 O(NMK)이다.
 
각 턴마다 수행되는 주요 연산은 다음과 같다.
공격자 선정: O(NM)
수비자 선정: O(NM)
레이저 경로 탐색(BFS): O(NM)
포탑 수리 및 상태 탐색: O(NM)
 
즉 각 턴에서 수행되는 전체 연산은 O(NM) 시간 안에 수행되며, 이를 최대 K턴 반복하므로 전체 시간 복잡도는 O(NMK)이다.
 
전체 공간 복잡도는 포탑 상태를 저장하는 board 배열과 BFS 과정에서 사용하는 queue, parent 등의 자료구조를 포함하여 O(NM)이다.

import sys,math
from collections import deque
input=sys.stdin.readline
INF=math.inf

Position=tuple[int,int]
class Adaptor():
    def read_parameter(self):
        N,M,K=map(int,input().split())
        self.N=N
        self.M=M
        self.K=K
        return N,M,K
    def read_board(self):
        raw_board_data=[list(map(int,input().split())) for _ in range(self.N)]
        board=[[[0,0] for _ in range(self.M)] for _ in range(self.N)]
        for x in range(self.N):
            for y in range(self.M):
                board[x][y][0]=raw_board_data[x][y]
        return board

class Controller():
    def __init__(self,K,service):
        self.K=K
        self.service=service
    def run(self):
        for turn in range(1,self.K+1):
            attacker=self.service.choose_attacker(turn)
            defender=self.service.choose_defender(attacker)
            is_success,victims=self.service.attack_laser(attacker,defender)
            if not is_success:
                victims=self.service.attack_cannon(attacker,defender)
            related_turrets={attacker,defender}|victims
            unrelated_turrets=self.service.get_all_undestroyed_turret()-related_turrets
            self.service.repair_turrets(unrelated_turrets)
            if self.service.count_unbroken_turret()==1:
                break
        print(self.service.get_strongest_turret_power())

class Service():
    def __init__(self,N,M,repository):
        self.repository=repository
        self.handicap=N+M
    def choose_attacker(self,turn:int)->Position:
        ''' choose attacker, record last attack timing and give handicap '''
        attacker:Position=self.repository.get_weakest_turret()
        self.repository.update_last_attack(attacker,turn)
        self.repository.update_power(attacker,self.handicap)
        return attacker
    def choose_defender(self,attacker:Position)->Position:
        ''' choose defender excepting attacker itself '''
        return self.repository.get_strongest_turret(attacker)
    def attack_laser(self,attacker:Position,defender:Position)->tuple[bool,set[Position]]:
        is_exist,affected_turrets=self.repository.get_shortest_path(attacker,defender)
        if not is_exist:
            return False,set()
        damage:int=self.repository.get_power(attacker)
        splash_damage:int=damage//2
        self.repository.update_power(defender,-damage)
        for turret in affected_turrets:
            self.repository.update_power(turret,-splash_damage)
        return True,affected_turrets
    def attack_cannon(self,attacker:Position,defender:Position)->set[Position]:
        neighbor:set[Position]=self.repository.get_neighbor(defender) # this return except defender
        affected_turrets=neighbor-{attacker}
        damage:int=self.repository.get_power(attacker)
        splash_damage:int=damage//2
        self.repository.update_power(defender,-damage)
        for turret in affected_turrets:
            self.repository.update_power(turret,-splash_damage)
        return affected_turrets
    def get_all_undestroyed_turret(self)->set[Position]:
        return self.repository.get_all_undestroyed_turret()
    def repair_turrets(self,turrets:set[Position])->None:
        for turret in turrets:
            self.repository.update_power(turret,1)
    def count_unbroken_turret(self)->int:
        return self.repository.count_unbroken_turret()
    def get_strongest_turret_power(self)->int:
        return self.repository.get_strongest_turret_power()
    
class Turret():
    POWER=0
    LAST_ATTACK=1

class Repository():
    def __init__(self,N,M,board):
        self.N=N
        self.M=M
        self.board=board
    def get_neighbor(self,entity:Position)->set[Position]:
        ''' returns neighbor except entitiy itself '''
        neighbor=set()
        cx,cy=entity
        for dx in [-1,0,1]:
            for dy in [-1,0,1]:
                if dx==0 and dy==0:
                    continue
                nx,ny=(cx+dx)%self.N,(cy+dy)%self.M
                neighbor.add((nx,ny))
        return neighbor
    def is_alive(self,x,y)->bool:
        return self.board[x][y][Turret.POWER]>0
    def get_weakest_turret(self)->Position:
        # ( power, -last_attack, -(x+y), -y, x, y )
        best=INF,INF,INF,INF,INF,INF
        for x in range(self.N):
            for y in range(self.M):
                if not self.is_alive(x,y):
                    continue
                cur=self.board[x][y][Turret.POWER],-self.board[x][y][Turret.LAST_ATTACK],-(x+y),-y,x,y
                best=min(best,cur)
        return best[-2:]
    def update_last_attack(self,entity:Position,turn:int)->None:
        cx,cy=entity
        self.board[cx][cy][Turret.LAST_ATTACK]=turn
    def update_power(self,entity:Position,amount:int)->None:
        cx,cy=entity
        self.board[cx][cy][Turret.POWER]+=amount
    def get_strongest_turret(self,entity:Position)->Position:
        # ( power, -last_attack, -(x+y), -y, x, y )
        best=-INF,-INF,-INF,-INF,-INF,-INF
        for x in range(self.N):
            for y in range(self.M):
                if (x,y)==entity:
                    continue
                if not self.is_alive(x,y):
                    continue
                cur=self.board[x][y][Turret.POWER],-self.board[x][y][Turret.LAST_ATTACK],-(x+y),-y,x,y
                best=max(best,cur)
        return best[-2:]
    def get_shortest_path(self,start:Position,end:Position)->tuple[bool,set[Position]]:
        # BFS
        queue=deque()
        parent=dict()
        queue.append(start)
        parent[start]=None
        while queue:
            cx,cy=queue.popleft()
            if (cx,cy)==end:
                path=set()
                cur=parent[end]
                while cur!=start:
                    path.add(cur)
                    cur=parent[cur]
                return True,path
            for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                nx,ny=(cx+dx)%self.N,(cy+dy)%self.M
                if (nx,ny) in parent:
                    continue
                if not self.is_alive(nx,ny):
                    continue
                queue.append((nx,ny))
                parent[(nx,ny)]=(cx,cy)
        return False,set()
    def get_power(self,entity:Position)->int:
        cx,cy=entity
        return self.board[cx][cy][Turret.POWER]
    def get_all_undestroyed_turret(self)->set[Position]:
        undestroyed_set=set()
        for x in range(self.N):
            for y in range(self.M):
                if self.is_alive(x,y):
                    undestroyed_set.add((x,y))
        return undestroyed_set
    def count_unbroken_turret(self)->int:
        count=0
        for x in range(self.N):
            for y in range(self.M):
                if self.is_alive(x,y):
                    count+=1
        return count
    def get_strongest_turret_power(self)->int:
        best=-INF
        for x in range(self.N):
            for y in range(self.M):
                cur=self.board[x][y][Turret.POWER]
                best=max(best,cur)
        return best

# INPUT
adaptor=Adaptor()
N,M,K=adaptor.read_parameter()
board=adaptor.read_board()

# CONSTRUCT
repository=Repository(N,M,board)
service=Service(N,M,repository)
controller=Controller(K,service)

# RUN
controller.run()

 
 

What I Learned

1. 튜플 우선순위 트릭
min/max로 다중 조건을 처리할 때는 기준 방향을 하나로 통일하자.
예를 들어 min 기준이라면 “작을수록 좋은 값”은 그대로 두고, “클수록 좋은 값”은 음수를 붙여 정렬 방향을 뒤집는다.

2. 최단 경로 탐색
가중치가 모두 동일한 그래프에서 최단 경로를 구할 때는 DFS가 아니라 BFS를 사용해야 한다.
DFS는 먼저 발견한 경로를 반환할 수는 있지만, 그 경로가 최단 경로임을 보장하지 못한다.

3. 우선순위가 적용되는 대상 구분
아기상어 문제는 같은 거리의 후보 노드들 중 어떤 노드를 선택할지가 중요했기 때문에, 동일 depth의 후보를 모아 비교해야 했다.

반면 이 문제는 도착 노드가 고정되어 있고, 같은 최단거리 경로들 중 어떤 경로를 선택할지가 중요했다.
따라서 BFS에서 인접 정점을 우/하/좌/상 순서로 enqueue하면, 탐색 우선순위가 곧 경로 우선순위가 되어 최초로 발견한 경로가 최적 경로가 된다.