[삼성 기출] 고대 문명 유적 탐사

 

Key Idea

이 문제는 어려운 알고리즘이 아니라 상태를 정확하게 다루는 구현력을 요구하는 문제이다.

회전 단계에서는 3x3 격자의 중심점을 기준으로 상대 좌표를 구하여 회전된 이후의 상태를 갱신하여야 하고,

유물 획득 단계에서는 같은 종류의 유물 조각들을 BFS/DFS를 이용하여 connected_component를 구할 수 있어야 했다.

 

처음에는 회전 단계에서 회전 중심을 원점으로 착각하는 실수를 했다.

하지만 이 문제에서는 원점 중심 회전이 아니라, 3x3 격자의 중앙을 회전 중심으로 삼으므로, 이 중앙점을 기준으로 한 상대 좌표를 적용하여야 한다.

 

코딩테스트 기출 문제 설명: 고대 문명 유적 탐사 | 코드트리

 

Architecture

요구사항을 분석한 뒤, SoC(Separation of Concerns) 원칙에 따라 Layer를 분리하였다.

1. Controller : 실행 흐름을 책임진다.

2. Service : 비즈니스 로직을 책임진다.

3. Repository : 상태의 저장 및 변경을 책임진다.

 

또한 생성자 DI(Dependency Injection)를 적용하여 상위 객체가 하위 객체를 직접 생성하지 않게 함으로써, 컴포넌트 간 결합도를 낮추었다.

 

UML

 

 

Implementation

 

회전 로직

 

각 좌표들을 선택한 중심점을 기준으로 한 상대 좌표를 구하여, degree 만큼 회전을 하는 코드이다.

회전 연산은 함수 합성에 대해 닫혀있는 군(Group) 구조를 가지므로, 90도 회전 연산을 기본 단위 연산으로 정의하고 이를 반복 합성하여 임의의 각도 회전을 구현하였다.

 

def rotate(self,cx,cy,degree)->None:
    def _turn90(cx,cy)->None:
        new_board=deepcopy(self.board)
        for rx in range(-1,2):
            for ry in range(-1,2):
                new_board[cx+ry][cy-rx]=self.board[cx+rx][cy+ry]
        self.board=new_board
    while degree!=0:
        _turn90(cx,cy)
        degree-=90

 

 

 

connect-component 탐색 로직

 

cc는 DFS/BFS/DSU로 진행할 수 있다.

DSU는 연결 관계가 동적으로 변하는 online 상황에서 특히 유용하다.

그러나 이 문제는 탐색 시점의 보드 상태가 변하지 않으므로 offline 그래프 탐색 문제로 볼 수 있다.

또한 DSU를 사용할 경우 부모의 위치를 저장하는 배열을 위한 추가 메모리만 필요하고 시간 복잡도에서 얻는 이점이 크지 않다고 판단하여 사용하지 않았다.

DFS/BFS/DSU의 시간복잡도는 O(N^2) 으로 동일한 바, 재귀적으로 탐색 로직을 함수 형태로 표현할 수 있는 DFS를 사용하여 가독성을 높였다.

 

아래의 P 함수는 미방문 셀을 방문하여 연결된 요소의 좌표 배열을 반환하는 함수이다.

이때 방문 처리에 대한 시작 책임은 호출자에 두고, P 함수는 이미 방문이 시작된 상태에서 탐색을 확장하는 역할만 수행하도록 함수의 책임을 "탐색"으로 한정하였다.

 

def P(cx,cy,visited)->list:
    same_group=[(cx,cy)]
    for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
        nx,ny=cx+dx,cy+dy
        if 0<=nx<N and 0<=ny<N:
            if (nx,ny) not in visited:
                if self.board[nx][ny]==self.board[cx][cy]:
                    visited.add((nx,ny))
                    same_group.extend(P(nx,ny,visited))
    return same_group

 

 

CODE

 

# 20260501 REFACTORTING
import sys
from collections import deque
from copy import deepcopy
input=sys.stdin.readline

K,M=map(int,input().split())
N=5
board=[list(map(int,input().split())) for _ in range(N)]
queue=deque(list(map(int,input().split())))


class Controller():
    def __init__(self,K,service):
        self.K=K
        self.service=service
    def run(self):
        answer=[]
        for _ in range(K):
            self.service.explore_ruins()
            ret=self.service.get_artifact()
            if ret==0:
                break
            answer.append(ret)
        print(*answer)

class Service():
    def __init__(self,repository):
        self.repository=repository

    def explore_ruins(self)->None:
        best=float("inf"),float("inf"),float("inf"),float("inf") # -score,degree,y,x take min
        for x in range(1,N-1):
            for y in range(1,N-1):
                for degree in [90,180,270]:
                    self.repository.rotate(x,y,degree)
                    score=len(self.repository.get_connected_component())
                    best=min(best,(-score,degree,y,x))
                    self.repository.rotate(x,y,360-degree)
        _,degree,y,x=best
        self.repository.rotate(x,y,degree)

    def get_artifact(self)->int:
        result=0
        while True:
            cc=self.repository.get_connected_component()
            if len(cc)==0:
                break
            result+=len(cc)
            self.repository.update(cc)
        return result


class Repository():
    def __init__(self,board,queue):
        self.board=board
        self.queue=queue

    def rotate(self,cx,cy,degree)->None:
        def _turn90(cx,cy)->None:
            new_board=deepcopy(self.board)
            for rx in range(-1,2):
                for ry in range(-1,2):
                    new_board[cx+ry][cy-rx]=self.board[cx+rx][cy+ry]
            self.board=new_board
        while degree!=0:
            _turn90(cx,cy)
            degree-=90
        
    def get_connected_component(self)->list:
        
        def P(cx,cy,visited)->list:
            same_group=[(cx,cy)]
            for dx,dy in [(-1,0),(1,0),(0,1),(0,-1)]:
                nx,ny=cx+dx,cy+dy
                if 0<=nx<N and 0<=ny<N:
                    if (nx,ny) not in visited:
                        if self.board[nx][ny]==self.board[cx][cy]:
                            visited.add((nx,ny))
                            same_group.extend(P(nx,ny,visited))
            return same_group

        valid_connected_component=[]
        visited=set()
        for x in range(N):
            for y in range(N):
                if (x,y) not in visited:
                    visited.add((x,y))
                    same_group=P(x,y,visited)  
                    if len(same_group)>=3:
                        valid_connected_component.extend(same_group)

        valid_connected_component.sort(key=lambda x:(x[1],-x[0]))
        
        return valid_connected_component
        
        
    def update(self,cc:list):
        for x,y in cc:
            item=self.queue.popleft()
            self.board[x][y]=item



repository=Repository(board,queue)
service=Service(repository)
controller=Controller(K,service)

controller.run()

 

시간 복잡도는 O(KN^4)이다.

각 턴 마다 각 점 O(N^2) 을 회전 중심으로 삼고, 3번의 회전 연산을 진행하며, DFS로 connected component 탐색을 수행하는데 O(N^2) 이 걸린다.

따라서 한 턴의 시간 복잡도는 O(N^2 * 3 * N^2)=O(N^4)이고, 이를 K번 반복하므로 전체 시간 복잡도는 O(KN^4)이다.

 

What I Learned

 

1. 회전 중심을 제대로 파악하자.

좌표 변환은 "어디를 기준으로 변환하는가" 가를 명확히 해야한다. 또한 실제 테스트 케이스를 그려서 검증하자.

 

2. 객체지향적 접근은 설계 능력을 보는 삼성의 코딩테스트에 효과적이다.

삼성은 단순한 알고리즘보다 상태 관리와 설계 능력을 요구한다. 레이어를 나누어 각 레이어의 책임을 명확히 하자.

 

3. 사고력을 더 키우자.

전체 구조는 잡을 수 있었지만, 회전 기준, 정렬 우선순위의 세부 규칙에서 지구력이 약해지며 흔들리는 부분이 있었다.

 

4. 동일한 연산은 함수 호출로 재사용할 수 있다.

degree 별로 case를 나누는 것도 좋지만, 회전 연산이 군(Group) 구조이기 때문에 같은 함수를 계속 호출하면 된다.