[코드트리] 파이썬 - 루돌프의 반란

코드트리 - 루돌프의 반란

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

 

 

소요시간 : 3시간 40

# 접근 방법

• 삼성 SW 대비하여 풀었는데 다른 문제보다 구현이 조금 오래걸렸다.
  • 특히, 산타와 루돌프가 움직인 후 충돌 체크를 하나의 함수로 하다보니 로직이 꼬인 부분이 있었고 시간을 많이 잡아먹었다.
  • 설계 단계에서 조금 더 신중하고 확실하게 접근해야 되겠다..
• 우선 진행 방향을 기록해두어야 하므로 헷갈리지 않게 매크로처럼 up, right ~ 대각선 방향을 모두 적어주었다.
• 입력받는 루돌프와 산타의 위치를 arr에 행과 열을 -1씩 해서 기록해두고, loc_rudolp와 loc_santa에도 기록해주었다.
• 또한 점수를 기록할 score_santa, 아웃과 기절을 기록할 flag_santa_out, flag_puase 리스트도 만들어주었다.
• M번동안 진행을 하며 아래 로직을 거친다.
• reset : 기절했던 산타가 2턴이 지났는지 확인하고 다시 움직일 수 있게 해준다.
• check_exit : 모든 산타가 아웃되었는지 확인 후에 모두 아웃되었다면 즉시 종료해준다.
• move_rudolp
  • 탈락하지 않은 모든 산타를 순회하며 거리를 비교해준다.
  • 가장 가까운 산타를 찾기 위하여 check_direct, change_santa 함수를 사용해주었다.
  • 가장 가까운 산타를 찾은 후에, 원래 자리를 0으로 만들고 이동할 자리가 비었다면 바로 -1로 변경, 아니라면 collision 함수를 실행해준다.
  • 이 때, 루돌프가 이동할 곳의 산타 번호를 넣었는데 실수로 -1을 넣어 루돌프가 중복해서 생겼었다.
• collsion
  • 루돌프, 산타에 따라 가중치를 달리해주고 score에 더해준다.
  • pause 리스트에 현재 턴을 기록해주고, move_interaction 함수를 실행해준다./
• move_interaction
  • 가중치만큼 떨어진 좌표를 ni, nj에 기록한다.
  • 만약 arr을 벗어나면 바로 탈락시키고 아니라면, 격자를 벗어나지 않는 동안 while 루프를 돌려준다.
  • 이동할 공간이 비었다면, 산타를 넣어주고 바로 종료
  • 아니라면, 이동할 곳의 산타를 기록해주고 현재 산타를 해당 좌표에 넣어준다.
• move_santa
  • 기절이거나 탈락하지 않은 모든 산타를 루돌프와 가까워 지는 방향으로 이동시키기 위하여 check_direct함수를 사용해준다.
  • 다만, return 값이 루돌프 기준이므로 상하좌우의 경우 +2 % 4를 이용하여 반대로 변경해주고, 대각선 이동의 경우 조건 처리를 해주고 우선 순위가 빠른 방향부터 기록해주었다.
  • 이동할 방향을 정해주고 해당 좌표가 비었다면 바로 이동
  • 아니라면 마찬가지로 collision 함수를 실행해준다.
• plus_score
  • 탈락하지 않은 산타에게 모두 1점을 더해준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

# 상(0), 우(1), 하(2), 좌(3), 좌상(4), 우상(5), 좌하(6), 우하(7)
UP = 0
RIGHT = 1
DOWN = 2
LEFT = 3
LEFT_UP = 4
RIGHT_UP = 5
LEFT_DOWN = 6
RIGHT_DOWN = 7

RUDOLP = 0
SANTA = 1

def move_rudolp(r, turn):
    global loc_rudolp
    ri, rj = r
    min_dist = float('inf')
    direct = -1
    santa_num = -1
    for i in range(1, P+1):
        if flag_santa_out[i] == True:
            continue
        si, sj = loc_santa[i]
        now_dist = abs(si-ri) ** 2 + abs(sj-rj) ** 2
        if now_dist < min_dist:
            min_dist = now_dist
            santa_num = i
            direct = check_direct(ri, rj, si, sj)
        elif now_dist == min_dist:
            santa_num = change_santa(santa_num, i)
            direct = check_direct(ri, rj, *loc_santa[santa_num])

    ni, nj = ri+di[direct], rj+dj[direct]
    arr[ri][rj] = 0
    loc_rudolp = [ni, nj]
    if arr[ni][nj] == 0:
        arr[ni][nj] = -1
    else:
        collision(turn, direct, RUDOLP, arr[ni][nj], ni, nj)

def change_santa(before, after):
    bi, bj = loc_santa[before]
    ai, aj = loc_santa[after]
    if bi > ai:
        return before
    elif bi == ai:
        if bj > aj:
            return before
        else:
            return after

    else:
        return after

def check_direct(ri, rj, si, sj):
    # 행이 같으면
    if ri == si:
        # 루돌프가 더 오른쪽에 있으면 왼쪽으로 진행
        if rj > sj:
            return LEFT
        else:
            return RIGHT

    elif rj == sj:
        # 루돌프가 아래에 있으면 위로 진행
        if ri > si:
            return UP
        else:
            return DOWN

    else:
        # 오른쪽 아래에 루돌프가 존재
        if ri > si:
            if rj > sj:
                return LEFT_UP
            else:
                return RIGHT_UP

        elif ri < si:
            if rj > sj:
                return LEFT_DOWN
            else:
                return RIGHT_DOWN



def move_santa(turn):
    global loc_rudolp, loc_santa
    for i in range(1, P+1):
        if flag_pause[i] > 0 or flag_santa_out[i] == True:
            continue
        si, sj = loc_santa[i]
        ri, rj = loc_rudolp
        direct = check_direct(ri, rj, si, sj)
        if direct >= 4:
            if direct == 4:
                direct = [RIGHT, DOWN]
            elif direct == 5:
                direct = [DOWN, LEFT]
            elif direct == 6:
                direct = [UP, RIGHT]
            else:
                direct = [UP, LEFT]

        else:
            direct = [(direct+2) % 4]

        now_dist = abs(ri - si) ** 2 + abs(rj - sj) ** 2
        now_direct = -1
        for d in direct:
            ni, nj = si + di[d], sj + dj[d]
            if 0<=ni<N and 0<=nj<N and arr[ni][nj] <= 0:
                new_dist = abs(ri - ni) ** 2 + abs(rj - nj) ** 2
                if now_dist > new_dist:
                    now_dist = new_dist
                    now_direct = d

        if now_direct > -1:
            ni, nj = si + di[now_direct], sj + dj[now_direct]
            if arr[ni][nj] == 0:
                arr[si][sj] = 0
                arr[ni][nj] = i
                loc_santa[i] = [ni, nj]
            else:
                arr[si][sj] = 0
                collision(turn, (now_direct+2)%4, SANTA, i, ni, nj)


def collision(turn, direct, who, num, ni, nj):
    global loc_rudolp, loc_santa
    santa_num = num
    if who == RUDOLP:
        alpha = C
        arr[ni][nj] = -1
    else:
        alpha = D

    score_santa[santa_num] += alpha
    flag_pause[santa_num] = turn
    move_interaction(santa_num, ni, nj, direct, alpha)


def move_interaction(num, ni, nj, direct, al):

    ni += di[direct] * al
    nj += dj[direct] * al
    if not (0<=ni<N and 0<=nj<N):
        flag_santa_out[num] = True
        return

    while 0<=ni<N and 0<=nj<N:
        if arr[ni][nj] == 0:
            loc_santa[num] = [ni, nj]
            arr[ni][nj] = num
            return

        else:
            new_santa = arr[ni][nj]
            arr[ni][nj] = num
            loc_santa[num] = [ni, nj]
            num = new_santa
            ni += di[direct]
            nj += dj[direct]
            if not (0<=ni<N and 0<=nj<N):
                flag_santa_out[num] = True
                return 

def reset(turn):
    for i in range(1, P+1):
        if flag_pause[i] != -1 and flag_pause[i] + 1 < turn:
            flag_pause[i] = -1

def check_exit():
    for i in range(1, P+1):
        if not flag_santa_out[i]:
            return False

    return True

def plus_score():
    for i in range(1, P+1):
        if flag_santa_out[i] == False:
            score_santa[i] += 1

N, M, P, C, D = map(int, input().split())
a, b = map(int, input().split())
arr = [[0] * N for _ in range(N)]

loc_rudolp = [a-1, b-1]

# -1 = 루돌프, 1~P = 산타
arr[a-1][b-1] = -1
loc_santa = [[0, 0] for _ in range(P+1)]
score_santa = [0] * (P+1)
flag_santa_out = [False] * (P+1)
flag_pause = [-1] * (P+1)

for _ in range(P):
    a, b, c = map(int, input().split())
    loc_santa[a] = [b-1, c-1]
    arr[b-1][c-1] = a
# 상(0), 우(1), 하(2), 좌(3), 좌상(4), 우상(5), 좌하(6), 우하(7)
di, dj = [-1, 0, 1, 0, -1, -1, 1, 1], [0, 1, 0, -1, -1, 1, -1, 1]

for m in range(1, M+1):
    reset(m)
    flag_exit = check_exit()
    if flag_exit:
        break
    move_rudolp(loc_rudolp, m)
    move_santa(m)
    plus_score()

print(*score_santa[1:])