[CodeTree] 루돌프의 반란 - 삼성 SW 역량테스트 2023 하반기 오후 1번 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 분석

• NxN 격자 위에서 루돌프가 먼저 이동하고, 그 후 1번 산타부터 P번 산타까지 순차적으로 이동하는 시뮬레이션 문제임.
• 두 칸의 거리는 유클리디언 거리로 계산함.
• 루돌프 움직임
  • 생존한 산타 중 가장 가까운 산타를 향해 1칸 이동함. 가까운 산타가 2명 이상일 경우, (행이 큰, 열이 큰) 우선순위에 따라 산타를 선택함.
  • 루돌프는 상하좌우 + 대각선 총 8방향으로 이동할 수 있으며, 선택된 산타와 가장 가까워지는 방향으로 이동.
  • 이동 시 
• 산타 움직임
  • 생존한 산타 중 기절하지 않은 산타에 한하여  1번 산타부터 P번 산타까지 순차적으로 이동함.
  • 산타 또한 루돌프에게 가장 가까워지는 방향으로 1칸 이동함.
  • 격자를 넘어가거나, 다른 산타가 있는 위치로는 이동할 수 없음.
  • 움직일 수 있는 칸이 있더라도 거리가 멀어지거나, 움직일 수 있는 칸이 없다면 이동하지 않음.
  • 산타는 상하좌우 4방향으로 이동할 수 있으며, (상, 하, 좌, 우) 우선순위에 따라 이동 방향을 결정함.
• 충돌
  • 산타 -> 루돌프 / 루돌프 -> 산타가 만나게 되면 충돌 과정이 발생하며, 해당 산타는 기절함.
  • 루돌프 -> 산타를 만나게 되면 해당 산타는 C점을 얻게 되며, 루돌프 이동 방향으로 C칸 밀려남.
  • 산타 -> 루돌프를 만나게 되면 해당 산타는 D점을 얻게 되며, 산타 이동 반대 방향으로 D칸 밀려남.
  • 밀려난 위치가 격자 밖이면 산타는 게임에서 탈락하며, 밀려난 위치에 다른 산타가 존재하면 상호작용 발생.
• 상호 작용
  • 밀려난 산타가 이동해야하는 위치에 다른 산타가 있으면, 기존에 있던 산타는 밀려난 산타가 온 방향으로 방향으로 1칸 밀려남.
  • 밀려난 후에도 산타가 계속 존재하면, 없을 때까지 반복적으로 수행함.
• 기절
  • 산타 -> 루돌프 / 루돌프 -> 산타가 충돌 할 때, 현재 턴이 K라면 K+1번 째 턴까지 기절함.
  • 기절한 산타는 이동할 수 없지만, 상호작용은 가능함.
  • 기잘한 산타를 루돌프가 공격할 수 있음.
• M번의 턴을 수행하거나, 수행 도중 생존한 산타가 없는 경우 게임을 즉시 종료하며, 1번부터 P번 산타까지 얻은 Score를 Return하는 문제.

 

문제 접근

조건이 굉장히 많고 연쇄 작용이 이뤄져야 하기 때문에, 쉬운 문제는 아니라고 느꼈음. 3차례의 시도 끝에 통과하게 되었고, 상당히 Edge Case들이 많이 발생할 수 있는 문제 중 하나임.

• 초기화 단계
  • 산타가 연쇄적으로 반응해야하는 요구사항이 있었기에, 몇 번 산타가 어느 칸에 존재하는지를 O(N)으로 탐색하면 비효율적일 것이라 판단하였음.
  • 이에, 산타의 pid로 위치를 접근할 수 있는 딕셔너리와, 해당 격자 좌표를 활용하여 산타의 pid를 접근할 수 있는 딕셔너리를 선언하여 관리.
  • 산타의 상태 (생존, 기절, 탈락)는 따로 딕셔너리로 관리.
• 루돌프 움직임
  • deer_attack()이라는 함수로 정의.
  • 산타를 순차적으로 탐색하며 생존한 산타와의 유클리디언 거리 측정 후 우선 순위에 따라 산타 선정.
  • 8방향 중 가장 가까운 거리의 방향으로 이동.
  • 이동하려는 위치에 산타가 없으면 루돌프 좌표 갱신 후 종료.
  • 산타가 있으면 충돌 + 상호작용 수행.
  • 최초 충돌 시에는 부딪힌 산타가 기절을 하지만, 상호 작용으로 인해 밀려나는 산타는 기절 상태로 변경되지 않는 부분을 빠르게 파악하지 못해 추가 제출 + 시간을 소모하게 됨.
• 산타 움직임
  
  • santa_attack()이라는 함수로 정의.
  • 산타를 순차적으로 탐색하며 루돌프로 이동할 수 있는 가장 가까운 위치를 탐색하고 이동함.
  • 이동한 위치에 산타가 있을 경우 충돌 + 상호작용이 일어남.
• 충돌
  
  • collapse()라는 함수로 구현.
  • (충돌 시작의 x좌표, y좌표, 방향, 거리)를 queue에 담아 충돌 과정을 수행함.
  • 밀려난 위치가 범위 밖이면 (산타 pid, x좌표, y좌표, -1=탈락)을 result 배열에 추가.
  • 밀려난 위치가 범위 밖은 아니면 (산타 pid, x좌표, y좌표, 2=기절) 을 result 배열에 추가.
  • 밀려난 위치에 산타가 있으면 queue에 넣어서 상호 작용 수행.
  • 충돌 및 상호작용으로 인해 변경된 산타의 정보를 담은 result 배열을 Return.
• 루돌프 / 산타가 움직인 후에 반복적으로 생존한 산타가 있는지 체크하는 과정 수행.
• 산타의 기절 조건 갱신 및 살아있는 산타는 1점씩 추가.

 

소스 코드

# defind lib
from collections import deque

# set value from input
N, M, P, C, D = map(int, input().split())
deer_x, deer_y = [num-1 for num in list(map(int, input().split()))]
direc = [(-1, 0), (0, 1), (1, 0), (0, -1), (1, -1), (-1, -1), (-1, 1), (1, 1)]
pid_to_pos, pos_to_pid, status, score = dict(), dict(), dict(), dict()

for _ in range(P): 
    pid, px, py = map(int, input().split())
    pid_to_pos[pid] = (px-1, py-1)
    pos_to_pid[(px-1, py-1)] = pid
    status[pid], score[pid] = 0, 0

# define function
def deer_attack():
    global deer_x, deer_y, pos_to_pid, pid_to_pos
    santa_dist = []
    for pid in range(1, P+1):
        if status[pid] == -1:
            continue
        px, py = pid_to_pos[pid]
        santa_dist.append(((deer_x-px)**2 + (deer_y-py)**2, px, py, pid))
    santa_dist.sort(key=lambda x: (x[0], -x[1], -x[2]))
    _, px, py, pid = santa_dist[0]

    _candits = []
    for didx in range(8):
        nx, ny = deer_x+direc[didx][0], deer_y+direc[didx][1]
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            continue
        _candits.append(((px-nx)**2 + (py-ny)**2, nx, ny, didx))
    _candits.sort(key=lambda x: (x[0]))
    _, ndeer_x, ndeer_y, ndeer_d = _candits[0]

    if (ndeer_x, ndeer_y) in pos_to_pid.keys():
        score[pos_to_pid[(ndeer_x, ndeer_y)]] += C
        result, flag = collase(ndeer_x, ndeer_y, ndeer_d, C), True
        for spid, snx, sny, nstat in result:
            if flag:
                origin_x, origin_y = pid_to_pos[spid]
                del pos_to_pid[(origin_x, origin_y)]
                status[spid], flag = nstat, False
            pos_to_pid[(snx, sny)] = spid
            pid_to_pos[spid] = (snx, sny)
            if nstat == -1:
                status[spid] = -1            
    deer_x, deer_y = ndeer_x, ndeer_y

def santa_attack():
    global deer_x, deer_y, pos_to_pid, pid_to_pos
    for pid in range(1, P+1):
        if status[pid] != 0:
            continue
        px, py = pid_to_pos[pid]
        bound, _candits = (deer_x-px)**2+(deer_y-py)**2, []
        for didx in range(4):
            nx, ny = px+direc[didx][0], py+direc[didx][1]
            tmp = (deer_x-nx)**2 + (deer_y-ny)**2
            if nx < 0 or nx >= N or ny < 0 or ny >= N or (nx, ny) in pos_to_pid.keys() or bound < tmp:
                continue
            nd = (0 if didx == 2 else 2) if didx in (0, 2) else (1 if didx == 3 else 3)
            _candits.append((tmp, didx, nx, ny, nd))

        if not _candits:
            continue

        _candits.sort(key=lambda x: (x[0], x[1]))
        _, _, nx, ny, nd = _candits[0]
        del pos_to_pid[(px, py)]
        pos_to_pid[(nx, ny)] = pid
        pid_to_pos[pid] = (nx, ny)

        if (nx, ny) == (deer_x, deer_y):
            score[pid] += D
            result, flag = collase(nx, ny, nd, D), True
            for spid, snx, sny, nstat in result:
                if flag:
                    origin_x, origin_y = pid_to_pos[spid]
                    del pos_to_pid[(origin_x, origin_y)]
                    status[spid], flag = nstat, False
                pos_to_pid[(snx, sny)] = spid
                pid_to_pos[spid] = (snx, sny)
                if nstat == -1:
                    status[spid] = -1

def collase(ndeer_x, ndeer_y, nd, dist):
    result = []
    dq = deque([(ndeer_x, ndeer_y, nd, dist)])
    while dq:
        cx, cy, cd, cdist = dq.popleft()
        cur_santa_pid = pos_to_pid[(cx, cy)]
        nx, ny = cx+direc[cd][0]*cdist, cy+direc[cd][1]*cdist

        # out of range
        if nx < 0 or nx >= N or ny < 0 or ny >= N:
            result.append((cur_santa_pid, nx, ny, -1))
            break
        
        # inbound
        result.append((cur_santa_pid, nx, ny, 2))
        if pos_to_pid.get((nx, ny), -1) != -1:
            dq.append((nx, ny, cd, 1))
    return result

def check_stun():
    for pid in status.keys():
        if status[pid] > 0:
            status[pid] -= 1

def add_score():
    for pid in pid_to_pos.keys():
        if status[pid] != -1:
            score[pid] += 1

def check_status():
    for pid, value in status.items():
        if value == -1:
            pid_to_pos[pid] = (-1, -1)
            continue
        return True
    return False

time = 0
while time < M:
    deer_attack()
    if not check_status():
        break
    santa_attack()
    if not check_status():
        break        
    check_stun()
    add_score()
    time += 1

print(*[score[i] for i in range(1, P+1)])