[삼성 기출] 왕실의 기사 대결

 
 

코딩테스트 기출 문제 설명: 왕실의 기사 대결 | 코드트리

 

Key Idea

이 문제의 핵심은 연쇄적으로 전파되는 상태 변화를 정확히 모델링할 수 있는지, 그리고 특정 기능들을 수행할 때 특정 상황에서는 무효화시키는 책임을 어느 계층이 갖도록 설계할 수 있는지에 있다고 생각한다.
 
문제 풀이는 하향식으로 진행하였으며, 문제를 이해한 뒤 Invariant를 설계한 뒤 상위 컴포넌트부터 하위 컴포넌트로 구체화해 나갔다.
 
Invariant 설계, 레이어 구성 설명에 이어 세부 컴포넌트들을 설명하겠다.
 
 

Invariant

1. 한번 입력 받은 board는 절대 수정되지 않는다.
2. 기사들의 정보를 저장하고 있는 knight는 항상 유효한 정보를 가지고 있어야 하며, 따라서 eager update가 일어나야 한다.
 
 

Architecture

 
레이어의 구성은 다음과 같다.
 
1. Adapter : 1-based로 주어진 문제의 입력에 대해, 다루기 쉬운 0-based로 변환하는 책임을 진다.
2. Controller : 쿼리에 따라 명령을 수행하는 책임을 진다. 비즈니스 로직과 데이터에 대해서는 의존하지 않아야 한다.
3. Service : 비즈니스 로직을 구현한다. 데이터에 대해 직접 접근할 수 없어야 한다.
4. Repository : 데이터를 상술한 Invariant 하에서 관리하는 책임을 진다. 필요 시 상위 컴포넌트를 위한 인터페이스를 제공해야 한다.
 
 

UML

 
 
 

Implementation - Adapter

어댑터 패턴은 별도의 클래스를 도입함으로써 코드 구조를 복합하게 할 수 있다는 단점이 있다.
그러나 입력이 1-based로 주어지는 문제를 내부적으로 0-based로 일관되게 처리하기 위해서 어댑터를 적용하였다.
이를 통하여 입력 변환 로직을 시스템의 경계에서 한번만 수행하고, 내부 로직에서는 일관된 0-based 좌표계만 사용할 수 있게 함으로써 가독성을 높이고 인지 부담을 줄일 수 있었다.
 
또한 입력의 L,N,Q는 전역 변수를 이용하여 모든 컴포넌트들에서 바로 참조하도록 할 수 있었으나,
컴포넌트들은 자신의 책임 밖의 변수들에 의존하면 안된다는 설계 원칙에 따라 전역 변수를 사용하지 않았다.
 
대신 어댑터 내부에서만 이들을 관리하도록 하였고, 세부 컴포넌트에서는 len(board)와 같은 국소적인 정보를 통해 필요한 연산을 수행하도록 구성하였다.
 

class Adapter():
    def read_parameter(self):
        L,N,Q=map(int,input().split())
        self.L=L
        self.N=N
        self.Q=Q
    def read_board(self)->list[list[int]]:
        board=[list(map(int,input().split())) for _ in range(self.L)]
        return board
    def read_knights(self)->dict[int,list[int]]:
        knights=dict()
        raw_knights_data=[list(map(int,input().split())) for _ in range(self.N)]
        for idx, (r,c,h,w,k) in enumerate(raw_knights_data):
            knights[idx]=[r-1,c-1,h,w,k,0]
        return knights
    def read_queries(self)->list[tuple[int,int]]:
        raw_query_data=[list(map(int,input().split())) for _ in range(self.Q)]
        quries=[(i-1,d) for i,d in raw_query_data]
        return quries

 
 

Implementation - Controller

입력으로 주어진 쿼리를 순차적으로 실행하여, 시스템의 전체 흐름을 제어하는 책임을 가진다.
따라서 비즈니스 로직이나 상태 관리에 대해서는 알지 못하도록 구성하였고, 명령 수행에 필요한 최소한의 정보에만 의존하도록 설계하였다.
또한 변수명과 함수명은 사람을 위한 인터페이스라고 생각하여, Controller가 인지할 수 있는 추상화 수준에 맞게 명명함으로써 컴포넌트의 책임 범위를 명확히 드러내고자 하였다.
 

class Controller():
    def __init__(self,service,queries):
        self.service=service
        self.queries=queries
    def run(self):
        for id, direction in self.queries:
            self.service.move_knight(id,direction)
        self.service.report_result()

 
 
 

Implementation - Service

비즈니스 로직을 구현하고, 명령 수행에 필요한 기능을 제공하는 책임을 가진다.
이 과정에서 상태를 직접 조작하거나 접근하지 않고, 반드시 Repository가 제공하는 인터페이스를 통해 상태를 조회하고 변경하도록 구성하였다. 
이를 통해 상태 관리의 책임을 Repository에 위임하고, Service는 비즈니스 규칙에만 집중할 수 있도록 하여 컴포넌트의 책임을 명확히 분리하였다.

class Service():
    def __init__(self,repository):
        self.repository=repository
    def move_knight(self,id,direction):
        if self.repository.is_alive(id):
            affected_group=self.repository.get_affected_group(id,direction)
            self.repository.move_affected_group(affected_group,direction)
            affected_group.discard(id)
            self.repository.update_group(affected_group)
    def report_result(self):
        print(self.repository.get_alive_total_damage())

 
 
 
 

Implementation - Repository

 
상태를 직접 소유하고 관리하는 계층으로, Service를 위한 상태 조회, 변경 인터페이스를 제공한다.
모든 상태 변경은 Repository를 통해서만 수행되며, 이 과정에서 Invariant가 유지하도록 보장하였다.
 
아래는 기사 이동 시 발생하는 연쇄 작용을 구현하기 위한 함수이다.
연쇄적으로 밀리는 구조는 하위 상태가 동일한 형태의 문제로 반복되기 때문에, 수학적 귀납법에 기반한 재귀 방식으로 구현하였다.
이때 움직일 수 없었다면 빈 그룹의 id 집합을 반환하도록 하여 정상적인 이동 결과와 구분하고, 이를 통해 하위 호출에서 발생한 실패가 상위 호출로 전파될 수 있도록 하였다.
 

def get_affected_group(self,id,direction)->set:
    ''' return affected group id set if it can move '''
    ''' return empty set if it cannot move '''
    dx,dy=Repository.dir2delta[direction]
    sx,sy,h,w,_,_=self.knight[id]
    checked_area=set()
    for x in range(sx,sx+h):
        for y in range(sy,sy+w):
            nx,ny=x+dx,y+dy
            checked_area.add((nx,ny))

    # base condition (cannot move)
    N=len(self.board)
    for x,y in checked_area:
        if not (0<=x<N and 0<=y<N):
            return set()
        if self.board[x][y]==2:
            return set()

    overlapped_knights=set()
    for nxt_id in self.knight:
        if nxt_id==id:
            continue
        if not self.knight[nxt_id][Repository.K]>0:
            continue
        osx,osy,oh,ow,_,_=self.knight[nxt_id]
        for ox in range(osx,osx+oh):
            for oy in range(osy,osy+ow):
                if (ox,oy) in checked_area:
                    overlapped_knights.add(nxt_id)

    # base condition (no one is overlapped)
    if len(overlapped_knights)==0:
        return {id}
        
        # recursion
        affected_set={id}
        for nxt_id in overlapped_knights:
            nxt_group=self.get_affected_group(nxt_id,direction)
            if len(nxt_group)==0:
                return set()
            affected_set.update(nxt_group)
        
        return affected_set

 
 
 

CODE

 
전체 코드는 아래와 같으며, 시간복잡도는 get_affected_group 연산이 각 호출마다 O(NL^2)의 비용을 가지며 연쇄 작용으로 인하여 최악의 경우 N개의 기사가 모두 연결되어 재귀적으로 호출될 수 있다.
따라서 해당 연산의 최악 시간복잡도는 O(N^2 L^2)이며, 이것이 쿼리 Q번 반복되므로 전체 시간복잡도는 O(Q N^2 L^2) 이다.
 

import sys
input=sys.stdin.readline


class Adapter():
    def read_parameter(self):
        L,N,Q=map(int,input().split())
        self.L=L
        self.N=N
        self.Q=Q
    def read_board(self)->list[list[int]]:
        board=[list(map(int,input().split())) for _ in range(self.L)]
        return board
    def read_knights(self)->dict[int,list[int]]:
        knights=dict()
        raw_knights_data=[list(map(int,input().split())) for _ in range(self.N)]
        for idx, (r,c,h,w,k) in enumerate(raw_knights_data):
            knights[idx]=[r-1,c-1,h,w,k,0]
        return knights
    def read_queries(self)->list[tuple[int,int]]:
        raw_query_data=[list(map(int,input().split())) for _ in range(self.Q)]
        quries=[(i-1,d) for i,d in raw_query_data]
        return quries
        

class Controller():
    def __init__(self,service,queries):
        self.service=service
        self.queries=queries
    def run(self):
        for id, direction in self.queries:
            self.service.move_knight(id,direction)
        self.service.report_result()

class Service():
    def __init__(self,repository):
        self.repository=repository
    def move_knight(self,id,direction):
        if self.repository.is_alive(id):
            affected_group=self.repository.get_affected_group(id,direction)
            self.repository.move_affected_group(affected_group,direction)
            affected_group.discard(id)
            self.repository.update_group(affected_group)
    def report_result(self):
        print(self.repository.get_alive_total_damage())

class Repository():

    R,C,H,W,K,D=0,1,2,3,4,5
    dir2delta={0:(-1,0),1:(0,1),2:(1,0),3:(0,-1)}

    def __init__(self,board,knight):
        self.board=board
        self.knight=knight

    def get_affected_group(self,id,direction)->set:
        ''' return affected group id set if it can move '''
        ''' return empty set if it cannot move '''
        dx,dy=Repository.dir2delta[direction]
        sx,sy,h,w,_,_=self.knight[id]
        checked_area=set()
        for x in range(sx,sx+h):
            for y in range(sy,sy+w):
                nx,ny=x+dx,y+dy
                checked_area.add((nx,ny))

        # base condition (cannot move)
        N=len(self.board)
        for x,y in checked_area:
            if not (0<=x<N and 0<=y<N):
                return set()
            if self.board[x][y]==2:
                return set()
        
        overlapped_knights=set()
        for nxt_id in self.knight:
            if nxt_id==id:
                continue
            if not self.knight[nxt_id][Repository.K]>0:
                continue
            osx,osy,oh,ow,_,_=self.knight[nxt_id]
            for ox in range(osx,osx+oh):
                for oy in range(osy,osy+ow):
                    if (ox,oy) in checked_area:
                        overlapped_knights.add(nxt_id)

        # base condition (no one is overlapped)
        if len(overlapped_knights)==0:
            return {id}
        
        # recursion
        affected_set={id}
        for nxt_id in overlapped_knights:
            nxt_group=self.get_affected_group(nxt_id,direction)
            if len(nxt_group)==0:
                return set()
            affected_set.update(nxt_group)
        
        return affected_set

        

    def move_affected_group(self,group:set,direction)->None:
        ''' move knights in the given group for given direction '''
        dx,dy=Repository.dir2delta[direction]
        for id in group:
            sx,sy,_,_,_,_=self.knight[id]
            self.knight[id][Repository.R]=sx+dx
            self.knight[id][Repository.C]=sy+dy

    def update_group(self,group:set):
        ''' update knigts' k considering traps in individual area '''
        for id in group:
            sx,sy,h,w,_,_=self.knight[id]
            for x in range(sx,sx+h):
                for y in range(sy,sy+w):
                    if self.board[x][y]==1:
                        self.knight[id][Repository.K]-=1
                        self.knight[id][Repository.D]+=1

    def is_alive(self,id)->bool:
        ''' return true if id is alive knight, else return false '''
        return self.knight[id][Repository.K]>0
    
    def get_alive_total_damage(self)->int:
        ''' return sum of knights' damges alive '''
        return sum(self.knight[id][Repository.D] for id in self.knight if self.knight[id][Repository.K]>0)
        


# INPUT - 0-based
adapter=Adapter()
adapter.read_parameter()
board=adapter.read_board()
knights=adapter.read_knights()
queries=adapter.read_queries()

# CONSTRUCT
repository=Repository(board,knights)
service=Service(repository)
controller=Controller(service,queries)

# RUN
controller.run()

 
 

What I Learned

1. 명령 무효화를 위한 책임을 어느 계층에게 둘지 명확히 설계하자.
2. Invariant 설계를 명확히 해야 한다.
3. 재귀 호출 시 본인의 자기 자신의 상태에 대한 처리를 해주자. (이 문제에서는 영향받는 set에 본인을 포함시키는 것)
4. 실패 전파 : 하위 호출에서 발생한 실패를 상위 호출에 전달하여야 한다. 이를 누락하면 논리 오류가 잘못된 상태를 만들고, 그 결과 런타임 에러까지 이어질 수 있다.
5. set()은 None이 아닌 Falsy 값이다. 따라서 빈 집합 여부는 if not group: 형태로 확인할 수 있다.
6. {}는 빈 딕셔너리이고, {id}는 원소 하나를 가진 집합이다.