[코드트리] 루돌프의 반란

https://www.codetree.ai/ko/frequent-problems/samsung-sw/problems/rudolph-rebellion/description

코딩테스트 기출 문제 설명: 루돌프의 반란 | 코드트리

 

dxy = [
    (-1,0),(0,1),(1,0),(0,-1),
    (-1,-1),(-1,1),(1,-1),(1,1)
]
def in_range(r, c):
    return 0<=r<N and 0<=c<N

def distance(r1, c1, r2, c2):
    return (r1-r2)**2 + (c1-c2)**2

class Santa:
    def __init__(self, num, r, c):
        self.num = num           # 산타 번호(0‑index)
        self.r, self.c = r, c    # 현재 위치
        self.fainted_turn = 0    # 이 턴까지 기절 (turn > fainted_turn 이면 정상)
        self.is_out = False      # 격자 밖 탈락?
        self.score = 0           # 누적 점수

    # -------------------------------------------------
    # 산타를 dir_num 방향으로 dist 칸 이동시키는 재귀 함수
    #   - 연쇄 밀림, 탈락 처리 포함
    # -------------------------------------------------
    def move(self, dir_num, dist):
        if dist == 0:
            return

        nr = self.r + dxy[dir_num][0] * dist
        nc = self.c + dxy[dir_num][1] * dist

        # 격자 밖 → 탈락
        if not in_range(nr, nc):
            self.is_out = True
            A[self.r][self.c] = None
            return

        # 착지 칸에 다른 산타가 있으면 1칸 추가 밀어내기(연쇄)
        if A[nr][nc] is not None:
            other_santa = santa_list[A[nr][nc]]
            other_santa.move(dir_num, 1)

        # 실제 위치 갱신
        A[self.r][self.c] = None
        self.r, self.c = nr, nc
        A[nr][nc] = self.num

    def distance(self, rudolph):
        return distance(self.r, self.c, rudolph[0], rudolph[1])
    # 현재 턴에 기절상태인가?
    def is_fainted(self):
        return self.fainted_turn >= turn


N, M, P, C, D = map(int, input().split())
# 게임판 크기, 게임 턴 수, 산타 수, 루돌프의 힘, 산타의 힘
r_r, r_c = map(int, input().split())
R = (r_r-1, r_c-1)
# 산타 정보
santa_list = [None] * P
for _ in range(P):
    num, r, c = map(int, input().split())
    santa_list[num-1] = Santa(num-1, r-1, c-1)
# 격자 / 0~P-1 = 산타번호
A = [[None]*N for _ in range(N)]
A[R[0]][R[1]] = -1 # 루돌프
for idx, s in enumerate(santa_list):
    A[s.r][s.c] = idx

# 루돌프 이동 함수
def move_rudolph():
    global R
    # 가장 가까운 산타 선택
    selected_santa = None
    for s in santa_list:
        if s.is_out:
            continue
        if (selected_santa is None or 
        (s.distance(R), -s.r, -s.c) < (selected_santa.distance(R), -selected_santa.r, -selected_santa.c)):
            selected_santa = s
    
    # 8방향 중 타겟에 더 가까워지는 1칸 선택
    selected_dir_num = -1
    min_distance = selected_santa.distance(R)
    for dir_num, (dr, dc) in enumerate(dxy):
        nr, nc = R[0]+dr, R[1]+dc
        if in_range(nr, nc) and distance(nr, nc, selected_santa.r, selected_santa.c) < min_distance:
            min_distance = distance(nr, nc, selected_santa.r, selected_santa.c)
            selected_dir_num = dir_num
    
    nr = R[0] + dxy[selected_dir_num][0]
    nc = R[1] + dxy[selected_dir_num][1]
    # 충돌시
    if A[nr][nc] is not None:
        s = santa_list[A[nr][nc]]
        s.fainted_turn = turn + 1
        s.score += C
        s.move(selected_dir_num, C)
    
    A[R[0]][R[1]] = None
    R = (nr, nc)
    A[nr][nc] = -1

def move_santa(santa: Santa):
    min_distance = santa.distance(R)
    selected_dir_num = -1
    for dir_num, (dr, dc) in enumerate(dxy[:4]):
        nr, nc = santa.r + dr, santa.c + dc
        if in_range(nr, nc) and (A[nr][nc] is None or A[nr][nc]==-1):
            if distance(nr, nc, R[0], R[1]) < min_distance:
                min_distance = distance(nr, nc, R[0], R[1])
                selected_dir_num = dir_num
    # 가까워질 수 있는 칸이 없으면 정지
    if selected_dir_num == -1:
        return
    nr = santa.r + dxy[selected_dir_num][0]
    nc = santa.c + dxy[selected_dir_num][1]

    # 빈칸
    if A[nr][nc] is None:
        santa.move(selected_dir_num, 1)
    # 루돌프칸 충돌
    else:
        santa.fainted_turn = turn + 1
        santa.score += D
        santa.move((selected_dir_num+2)%4, D-1)

def main():
    global turn
    for turn in range(1, M+1):
        move_rudolph()

        for s in santa_list:
            if not s.is_out and not s.is_fainted():
                move_santa(s)
        
        is_all_out = True
        for s in santa_list:
            if not s.is_out:
                s.score += 1
                is_all_out = False
        if is_all_out:
            break

    print(*[s.score for s in santa_list])

main()