노-트
[삼성 기출] 루돌프의 반란 본문
코딩테스트 기출 문제 해설: 루돌프의 반란 | 코드트리
코딩테스트 기출 문제 루돌프의 반란의 상세 해설과 예시 코드를 제공합니다. 다양한 접근 방식과 최적화 전략을 학습하세요.
www.codetree.ai
Key Idea
이 문제의 핵심은 엔티티 간의 상호작용으로 인한 효과를 코드로 구현할 수 있는가,
그리고 레이어별 책임 분리를 적절하게 설계하여 구현 과정의 인지 부담을 낮출 수 있느냐 라고 생각한다.
이 문제의 경우는 일반적인 삼성 기출 문제들과 달리 board 배열이 입력에 주어지지 않는다. 이 점에서 설계 과정중 내부적으로 board 배열을 관리해야 하는지의 필요성 여부를 고민해 보았다.
board 배열이 필요한 본질적 이유는 엔티티가 움직인 위치에 다른 엔티티가 있는지를 파악하기 위함이다.
이 문제의 경우는 엔티티는 루들프 1개, 산타 P개 (<=30)로 매우 적기 때문에, board 배열을 이용한 O(1)의 조회와 단순 전수 조사의 O(P) 조회 성능 차이가 크지 않다고 판단하여 board 배열을 사용하지 않았다.
더욱이 문제에서 꼭 필요한 상태가 아닌 보조 상태를 관리하지 않음으로써 상태 불일치(Invariant 붕괴) 가능성을 최대한 줄이고자 하였고, O(N^2) 메모리를 아낄 수 있는 장점도 얻을 수 있었다.
Invariant
1. 딕셔너리 santa[id]=(x,y,score,last_stunned)는 항상 유효한 정보를 가지기 위해 eager update로 관리해주어야 한다. 특히 Repository 레이어만 딕셔너리에 직접 접근할 수 있게 캡슐화함으로써, data consistency를 지키고자 하였다.
2. rudolph=(x,y)도 역시 동일한 원칙으로 관리한다. 이외의 상태는 저장하지 않음으로써 consistency가 깨질 가능성을 줄이고 메모리 사용 또한 줄이고자 하였다.
Architecture
레이어의 구성은 다음과 같다.
1. Adapter : 1-based로 주어진 문제의 입력에 대해, 다루기 쉬운 0-based로 변환하는 책임을 진다.
2. Controller : 시뮬레이션을 수행하는 책임을 진다. 비즈니스 로직과 데이터에 대해서는 의존하지 않아야 한다.
3. Service : 비즈니스 로직을 구현한다. 데이터에 대해 직접 접근할 수 없어야 한다.
4. Repository : 데이터를 상술한 Invariant 하에서 Consistency 하게 관리하는 책임을 진다. 필요 시 상위 컴포넌트를 위한 상태 조회/수정 인터페이스를 제공해야 한다.
Implementation - Adapter
전역 변수는 코드의 어느 위치에서든 값이 수정될 수 있기 때문에 상태 추적을 어렵게 만들고 data consistency를 깨뜨릴 수 있는 위험한 안티패턴이라고 생각한다.
따라서 문제의 파라미터 N,M,P,C,D는 전역에서 직접 참조하지 않고, 입력 단계에서 한 번 읽은 뒤 필요한 객체의 생성자에 명시적으로 전달하는 방식으로 설계하였다. 이를 통해 레이어는 자신에게 필요한 값만 의존하게 되고, 코드 전체에서 암묵적으로 공유되는 상태를 제거하였다.
class Adaptor(): # converted to 0-based
def read_parameter(self):
N,M,P,C,D=map(int,input().split())
self.N=N
self.M=M
self.P=P
self.C=C
self.D=D
return N,M,P,C,D
def read_rudolph(self):
Rr,Rc=map(int,input().split())
return [Rr-1,Rc-1]
def read_santa(self):
raw_santa_data=[list(map(int,input().split())) for _ in range(self.P)]
santa=dict()
for Pn,Sr,Sc in raw_santa_data:
santa[Pn-1]=[Sr-1,Sc-1,0,-2]
return santa
Implementation - Controller
이 컴포넌트는 전체 시뮬레이션의 흐름을 책임진다.
각 턴마다 루돌프를 움직인 이후 산타가 움직일 수 있는 조건에 있다면 산타 또한 움직인다.
모든 이동이 종료된 뒤, 살아 있는 산타가 있다면 게임을 진행하고 이 과정에서 살아남은 산타들에게 점수를 주는 로직을 수행한다.
"살아남은 산타인지 판단하는 책임"을 Controller가 지게 설계하였다.
이를 통해 하위 컴포넌트인 Service의 함수들은 해당 산타가 살아남은 산타임을 보장받는 상태에서 호출되게 하였고, 이에 따라 각 함수 내부에서 반복적으로 생존 여부를 검증해야 하는 부담을 줄였다.
즉, 상위 레이어에서 호출 조건을 보장함으로써 하위 레이어의 구현 복잡도를 낮추고자 하였다.
class Controller():
def __init__(self,M,P,service):
self.M=M
self.P=P
self.service=service
def run(self): # TOTAL TIME COMPLEXITY = O(MP^2)
for turn in range(self.M):
self.service.move_rudolph(turn)
for id in range(self.P):
if self.service.is_can_move(id,turn):
self.service.move_santa(id,turn)
if not self.service.is_someone_left():
break
for id in range(self.P):
if self.service.is_alive(id):
self.service.give_surviving_bonus(id)
print(*self.service.get_total_score())
Implementation - Service
비즈니스 로직을 구현하며 Controller를 위한 인터페이스를 제공하는 책임을 진다.
또한 데이터에 대한 접근이 필요할 시에는 Repository에 위임함으로써 , 데이터 접근 경로를 단일화 하고 data consistency를 지키고자 하였다.
개발 과정에서는 각 컴포넌트를 구현하면서 필요한 하위 레이어의 인터페이스를 먼저 주석과 pass 키워드를 이용하여 명시하였다.
이를 통해 "어떤 기능이 필요하며", "해당 함수가 어떤 동작을 수행하고 어떤 반환값을 산출해야 하는지"를 먼저 설계한 뒤 구현에 들어갈 수 있었고, 전체 흐름을 먼저 고정한 상태에서 하위 기능을 점진적으로 채워 넣을 수 있음에 따라 구현 과정의 인지 부담을 줄일 수 있었다.
class Service():
def __init__(self,C,D,repository):
self.C=C
self.D=D
self.repository=repository
def move_rudolph(self,turn)->None:
''' move rudoplph according to problem's condition '''
id,d=self.repository.find_closest_santa()
self.repository.move_rudolph(d)
if self.repository.check_collision(id): # O(P^2)
self.repository.stun(id,turn)
self.repository.give_score(id,self.C)
self.repository.push(id,d,self.C)
def is_can_move(self,id,turn)->bool:
''' return bool indicating whether santa[id] can move in current turn '''
if self.repository.is_stunned(id,turn):
return False
if not self.repository.is_alive(id):
return False
return True
def move_santa(self,id,turn)->None: # O(P^2)
''' move santa[id] according to problem's condition '''
d=self.repository.find_closest_direction(id)
if d==-1: return
self.repository.move_santa(id,d)
if self.repository.check_collision(id):
self.repository.stun(id,turn)
self.repository.give_score(id,self.D)
self.repository.push(id,(d+4)%8,self.D) # opposite direction
def is_someone_left(self)->bool:
''' return bool indicating whether more than one santa has remained '''
return self.repository.is_someone_left()
def is_alive(self,id)->bool:
''' return bool indicating whether santa[id] is alive '''
return self.repository.is_alive(id)
def give_surviving_bonus(self,id)->None:
''' give one score to santa[id] '''
self.repository.give_score(id,1)
def get_total_score(self)->int:
''' get sum of all santas' score '''
return self.repository.get_total_score()
Implementation - Repository
데이터에 직접 접근할 수 있는 유일한 계층이며, Service를 위한 인터페이스를 제공하는 책임을 가진다.
방향 벡터와 방향 좌표의 변환 함수는 양방향 모두 staticmethod로 정의하였고, 거리 함수 또한 staticmethod로 정의함으로써 특정 인스턴스에 의존하지 않는 순수한 유틸리티 함수을 나타내었고 코드의 재사용성과 가독성을 높이고자 하였다.
연쇄 작용을 구현하는 push 함수의 경우는 파라미터에 몇 칸 밀렸는지(power) 에 대한 정보를 받도록 설계하였다.
이를 통하여 첫 호출시에는 임의의 값에 따른(C 혹은 D) 밀쳐진 효과를 구현할 수 있게 하였고, 이후 연쇄적인 호출부터는 문제에 명시된 대로 1칸씩 밀리는 것이 재귀적으로 구현되도록 하였다.
class Repository():
X,Y,SCORE,LAST_STUNNED=0,1,2,3
def __init__(self,N,P,rudolph,santa):
self.N=N
self.P=P
self.rudolph=rudolph # rudolph=X,Y
self.santa=santa # santa[id]=X,Y,SCORE,LAST_STUNNED
@staticmethod
def delta2dir(dx,dy)->int:
if dx<0 and dy==0: return 0
if dx<0 and dy>0: return 1
if dx==0 and dy>0: return 2
if dx>0 and dy>0: return 3
if dx>0 and dy==0: return 4
if dx>0 and dy<0: return 5
if dx==0 and dy<0: return 6
if dx<0 and dy<0: return 7
@staticmethod
def dir2delta(dir)->tuple[int,int]:
if dir==0: return -1,0
if dir==1: return -1,1
if dir==2: return 0,1
if dir==3: return 1,1
if dir==4: return 1,0
if dir==5: return 1,-1
if dir==6: return 0,-1
if dir==7: return -1,-1
@staticmethod
def get_distance(x1,y1,x2,y2):
return (x1-x2)**2+(y1-y2)**2
def find_closest_santa(self)->tuple[int,int]: # O(P)
''' return closest santa id, and direction toward him '''
best=INF,-INF,-INF,-INF # (min dist, - max x, - max y, santa id)
rx,ry=self.rudolph[Repository.X],self.rudolph[Repository.Y]
for id in self.santa:
if not self.is_alive(id):
continue
cx,cy=self.santa[id][Repository.X],self.santa[id][Repository.Y]
cur=Repository.get_distance(rx,ry,cx,cy),-cx,-cy,id
best=min(best,cur)
nx,ny,santa_id=-best[1],-best[2],best[3]
dx,dy=nx-rx,ny-ry
direction=Repository.delta2dir(dx,dy)
return santa_id,direction
def move_rudolph(self,direction)->None:
''' move rudolph into direction, have no resposiblility of collision check '''
dx,dy=Repository.dir2delta(direction)
self.rudolph[Repository.X]+=dx
self.rudolph[Repository.Y]+=dy
def check_collision(self,id)->bool:
''' return bool indicating collision between santa[id] and rudolph '''
return self.santa[id][Repository.X]==self.rudolph[Repository.X] \
and self.santa[id][Repository.Y]==self.rudolph[Repository.Y]
def give_score(self,id,score)->None:
''' give santa[id] to score'''
self.santa[id][Repository.SCORE]+=score
def push(self,id,direction,power)->None: # O(P^2)
''' push santa[id] into direction, have resposibility of chaining reaction '''
dx,dy=Repository.dir2delta(direction)
dx*=power
dy*=power
cx,cy=self.santa[id][Repository.X],self.santa[id][Repository.Y]
nx,ny=cx+dx,cy+dy
self.santa[id][Repository.X]=nx
self.santa[id][Repository.Y]=ny
overlapped_santa=-1
for nid in self.santa:
if nid==id or not self.is_alive(nid):
continue
if self.santa[nid][Repository.X]==nx and self.santa[nid][Repository.Y]==ny:
overlapped_santa=nid
break
if overlapped_santa==-1:
return
self.push(overlapped_santa,direction,1)
def stun(self,id,turn)->None:
''' stun santa[id] in current turn '''
self.santa[id][Repository.LAST_STUNNED]=turn
def is_stunned(self,id,turn)->bool:
''' return bool indicating santa[id] is now stunned '''
return turn<=self.santa[id][Repository.LAST_STUNNED]+1
def is_alive(self,id)->bool:
''' return bool indicating santa[id] is within board '''
return 0<=self.santa[id][Repository.X]<self.N \
and 0<=self.santa[id][Repository.Y]<self.N
def find_closest_direction(self,id)->int: # O(P)
''' return direction toward rudolph of santa[id] '''
''' return -1 if cannot move'''
ex,ey=self.rudolph[Repository.X],self.rudolph[Repository.Y]
sx,sy=self.santa[id][Repository.X],self.santa[id][Repository.Y]
cur_dist=Repository.get_distance(ex,ey,sx,sy)
best=cur_dist,INF # distance, dir
for dir in [0,2,4,6]:
dx,dy=Repository.dir2delta(dir)
nx,ny=sx+dx,sy+dy
if not (0<=nx<self.N and 0<=ny<self.N):
continue
is_other_santa=False
for nid in self.santa:
if nid==id:
continue
if self.santa[nid][Repository.X]==nx and self.santa[nid][Repository.Y]==ny:
is_other_santa=True
break
if is_other_santa:
continue
cur=Repository.get_distance(ex,ey,nx,ny),dir
best=min(best,cur)
if best[0]==cur_dist:
return -1
nxt_dir=best[1]
return nxt_dir
def move_santa(self,id,direction)->None:
''' move santa[id] into direction, has no respositiiliy of collision check '''
dx,dy=Repository.dir2delta(direction)
self.santa[id][Repository.X]+=dx
self.santa[id][Repository.Y]+=dy
def is_someone_left(self)->bool: # O(P)
''' return bool indicating whether any santa has remained '''
return any(self.is_alive(id) for id in self.santa)
def get_total_score(self)->list[int]: # O(P)
''' return list of santas' score '''
return [self.santa[id][Repository.SCORE] for id in range(self.P)]
CODE
전체 코드는 다음과 같다.
시간 복잡도는 각 턴마다 루돌프 이동, 산타 이동, 충돌 및 연쇄 작용 처리를 수행한다.
이때 연쇄 작용을 처리하는 push 함수는 재귀적으로 최대 P개의 산타를 밀 수 있으며 각 호출마다 겹치는 산타를 찾기 위해 최대 P개의 산타 정보를 확인하므로 최악의 경우 O(P^2)의 시간이 걸린다.
따라서 한 턴의 시간 복잡도는 O(P^2)가 지배적이며 총 M개의 턴을 수행하므로 전체 시간 복잡도는 O(MP^2)이다.
공간 복잡도는 산타 P개에 대한 딕셔너리가 지배적이며 별도의 NxN board 배열을 관리하지 않음으로 O(P)이다.
import sys,math
input=sys.stdin.readline
INF=math.inf
class Adaptor(): # converted to 0-based
def read_parameter(self):
N,M,P,C,D=map(int,input().split())
self.N=N
self.M=M
self.P=P
self.C=C
self.D=D
return N,M,P,C,D
def read_rudolph(self):
Rr,Rc=map(int,input().split())
return [Rr-1,Rc-1]
def read_santa(self):
raw_santa_data=[list(map(int,input().split())) for _ in range(self.P)]
santa=dict()
for Pn,Sr,Sc in raw_santa_data:
santa[Pn-1]=[Sr-1,Sc-1,0,-2]
return santa
class Controller():
def __init__(self,M,P,service):
self.M=M
self.P=P
self.service=service
def run(self): # TOTAL TIME COMPLEXITY = O(MP^2)
for turn in range(self.M):
self.service.move_rudolph(turn)
for id in range(self.P):
if self.service.is_can_move(id,turn):
self.service.move_santa(id,turn)
if not self.service.is_someone_left():
break
for id in range(self.P):
if self.service.is_alive(id):
self.service.give_surviving_bonus(id)
print(*self.service.get_total_score())
class Service():
def __init__(self,C,D,repository):
self.C=C
self.D=D
self.repository=repository
def move_rudolph(self,turn)->None:
''' move rudoplph according to problem's condition '''
id,d=self.repository.find_closest_santa()
self.repository.move_rudolph(d)
if self.repository.check_collision(id): # O(P^2)
self.repository.stun(id,turn)
self.repository.give_score(id,self.C)
self.repository.push(id,d,self.C)
def is_can_move(self,id,turn)->bool:
''' return bool indicating whether santa[id] can move in current turn '''
if self.repository.is_stunned(id,turn):
return False
if not self.repository.is_alive(id):
return False
return True
def move_santa(self,id,turn)->None: # O(P^2)
''' move santa[id] according to problem's condition '''
d=self.repository.find_closest_direction(id)
if d==-1: return
self.repository.move_santa(id,d)
if self.repository.check_collision(id):
self.repository.stun(id,turn)
self.repository.give_score(id,self.D)
self.repository.push(id,(d+4)%8,self.D) # opposite direction
def is_someone_left(self)->bool:
''' return bool indicating whether more than one santa has remained '''
return self.repository.is_someone_left()
def is_alive(self,id)->bool:
''' return bool indicating whether santa[id] is alive '''
return self.repository.is_alive(id)
def give_surviving_bonus(self,id)->None:
''' give one score to santa[id] '''
self.repository.give_score(id,1)
def get_total_score(self)->int:
''' get sum of all santas' score '''
return self.repository.get_total_score()
class Repository():
X,Y,SCORE,LAST_STUNNED=0,1,2,3
def __init__(self,N,P,rudolph,santa):
self.N=N
self.P=P
self.rudolph=rudolph # rudolph=X,Y
self.santa=santa # santa[id]=X,Y,SCORE,LAST_STUNNED
@staticmethod
def delta2dir(dx,dy)->int:
if dx<0 and dy==0: return 0
if dx<0 and dy>0: return 1
if dx==0 and dy>0: return 2
if dx>0 and dy>0: return 3
if dx>0 and dy==0: return 4
if dx>0 and dy<0: return 5
if dx==0 and dy<0: return 6
if dx<0 and dy<0: return 7
@staticmethod
def dir2delta(dir)->tuple[int,int]:
if dir==0: return -1,0
if dir==1: return -1,1
if dir==2: return 0,1
if dir==3: return 1,1
if dir==4: return 1,0
if dir==5: return 1,-1
if dir==6: return 0,-1
if dir==7: return -1,-1
@staticmethod
def get_distance(x1,y1,x2,y2):
return (x1-x2)**2+(y1-y2)**2
def find_closest_santa(self)->tuple[int,int]: # O(P)
''' return closest santa id, and direction toward him '''
best=INF,-INF,-INF,-INF # (min dist, - max x, - max y, santa id)
rx,ry=self.rudolph[Repository.X],self.rudolph[Repository.Y]
for id in self.santa:
if not self.is_alive(id):
continue
cx,cy=self.santa[id][Repository.X],self.santa[id][Repository.Y]
cur=Repository.get_distance(rx,ry,cx,cy),-cx,-cy,id
best=min(best,cur)
nx,ny,santa_id=-best[1],-best[2],best[3]
dx,dy=nx-rx,ny-ry
direction=Repository.delta2dir(dx,dy)
return santa_id,direction
def move_rudolph(self,direction)->None:
''' move rudolph into direction, have no resposiblility of collision check '''
dx,dy=Repository.dir2delta(direction)
self.rudolph[Repository.X]+=dx
self.rudolph[Repository.Y]+=dy
def check_collision(self,id)->bool:
''' return bool indicating collision between santa[id] and rudolph '''
return self.santa[id][Repository.X]==self.rudolph[Repository.X] \
and self.santa[id][Repository.Y]==self.rudolph[Repository.Y]
def give_score(self,id,score)->None:
''' give santa[id] to score'''
self.santa[id][Repository.SCORE]+=score
def push(self,id,direction,power)->None: # O(P^2)
''' push santa[id] into direction, have resposibility of chaining reaction '''
dx,dy=Repository.dir2delta(direction)
dx*=power
dy*=power
cx,cy=self.santa[id][Repository.X],self.santa[id][Repository.Y]
nx,ny=cx+dx,cy+dy
self.santa[id][Repository.X]=nx
self.santa[id][Repository.Y]=ny
overlapped_santa=-1
for nid in self.santa:
if nid==id or not self.is_alive(nid):
continue
if self.santa[nid][Repository.X]==nx and self.santa[nid][Repository.Y]==ny:
overlapped_santa=nid
break
if overlapped_santa==-1:
return
self.push(overlapped_santa,direction,1)
def stun(self,id,turn)->None:
''' stun santa[id] in current turn '''
self.santa[id][Repository.LAST_STUNNED]=turn
def is_stunned(self,id,turn)->bool:
''' return bool indicating santa[id] is now stunned '''
return turn<=self.santa[id][Repository.LAST_STUNNED]+1
def is_alive(self,id)->bool:
''' return bool indicating santa[id] is within board '''
return 0<=self.santa[id][Repository.X]<self.N \
and 0<=self.santa[id][Repository.Y]<self.N
def find_closest_direction(self,id)->int: # O(P)
''' return direction toward rudolph of santa[id] '''
''' return -1 if cannot move'''
ex,ey=self.rudolph[Repository.X],self.rudolph[Repository.Y]
sx,sy=self.santa[id][Repository.X],self.santa[id][Repository.Y]
cur_dist=Repository.get_distance(ex,ey,sx,sy)
best=cur_dist,INF # distance, dir
for dir in [0,2,4,6]:
dx,dy=Repository.dir2delta(dir)
nx,ny=sx+dx,sy+dy
if not (0<=nx<self.N and 0<=ny<self.N):
continue
is_other_santa=False
for nid in self.santa:
if nid==id:
continue
if self.santa[nid][Repository.X]==nx and self.santa[nid][Repository.Y]==ny:
is_other_santa=True
break
if is_other_santa:
continue
cur=Repository.get_distance(ex,ey,nx,ny),dir
best=min(best,cur)
if best[0]==cur_dist:
return -1
nxt_dir=best[1]
return nxt_dir
def move_santa(self,id,direction)->None:
''' move santa[id] into direction, has no respositiiliy of collision check '''
dx,dy=Repository.dir2delta(direction)
self.santa[id][Repository.X]+=dx
self.santa[id][Repository.Y]+=dy
def is_someone_left(self)->bool: # O(P)
''' return bool indicating whether any santa has remained '''
return any(self.is_alive(id) for id in self.santa)
def get_total_score(self)->list[int]: # O(P)
''' return list of santas' score '''
return [self.santa[id][Repository.SCORE] for id in range(self.P)]
# INPUT
adaptor=Adaptor()
N,M,P,C,D=adaptor.read_parameter()
rudolph=adaptor.read_rudolph()
santa=adaptor.read_santa()
# CONSTRUCT
repository=Repository(N,P,rudolph,santa)
service=Service(C,D,repository)
controller=Controller(M,P,service)
# MAIN
controller.run()
What I Learned
1. 레이어 별 책임분리를 통해 인지부담을 최소화할 수 있으며, 최근 이러한 구조화를 훨씬 더 수월하게 수행할 수 있음이 느껴진다.
2. 재귀 호출시 입력 파라미터에 현재 상황에 대한 정보를 함께 전달함으로써 별도의 보조 함수 없이 단일 함수 구조 안에서 연쇄 작용을 자연스럽게 표현할 수 있음을 배웠다.
3. 재귀 함수의 증명은 단순한 직관이 아니라 수학적 귀납법 관점에서 검증해야한다.
특히 1. base가 문제 조건에 올바르게 종료되는가. 2. 하부 호출이 올바르다고 가정했을때 현재(상부) 호출 또한 올바르게 상태 전이를 보장하는가.
4. 문제 이해 과정에서 직관을 수학적으로 검증하자.
이 문제의 경우에는 충돌을 구현하는 함수를 구현할 때 "가장 가까운 산타를 향해 이동했다면 충돌 또한 반드시 그 산타와 일어난다"는 사실을 먼저 증명할 필요가 있었다.
루돌프와 산타 S가 충돌했다고 하자.
충돌이 발생했다는 것은 루돌프가 S 방향으로 1칸 이동한 결과 두 엔티티의 좌표가 같아졌다는 의미이다.
또한 루돌프는 항상 “가장 가까운 산타”를 기준으로 이동 방향을 결정한다.
이때 다음과 같은 반례 가능성을 고려하였다
"루돌프는 더 가까운 다른 산타 S'를 향해 이동했지만, 이동 과정에서 우연히 S와 충돌하는 경우가 가능한가?"
하지만 이는 모순이다.
충돌이 일어나기 위해서는 이동 직전 루돌프와 S의 거리가 정확히 1칸 차이였어야 한다.
즉 S는 루돌프의 인접 칸에 존재하고 있었다는 뜻이다.
그런데 만약 동일한 이동 방향 상에 S보다 더 가까운 산타 S'가 존재했다면, S'는 루돌프와의 거리가 0칸이어야 한다.
즉 이미 루돌프와 같은 좌표에 존재하고 있었다는 의미가 된다.
하지만 문제 조건상 서로 다른 엔티티가 동일 좌표에서 시작하는 상태는 존재할 수 없으므로 이는 모순이다. (연쇄 효과에 의해 서로 다른 엔티티가 같은 좌표에 있을 수 있는 상황은 존재할 수 없다)
따라서 루돌프가 이동 후 충돌했다면, 그 충돌 대상은 반드시 “가장 가까운 산타”를 탐색하는 과정에서 선택된 바로 그 산타임이 보장된다는 결론을 얻을 수 있었고, 이를 기반으로 충돌 처리 로직을 안전하게 구현할 수 있었다.
'Problem Solving' 카테고리의 다른 글
| [LeetCode] 1674. Minimum Moves to Make Array Complementary (0) | 2026.05.14 |
|---|---|
| [삼성 기출] 왕실의 기사 대결 (0) | 2026.05.06 |
| [삼성 기출] 고대 문명 유적 탐사 (0) | 2026.04.30 |
