[코드트리] 루돌프의 반란 / Python(파이썬)

문제

https://www.codetree.ai/training-field/frequent-problems/problems/rudolph-rebellion/description?page=1&pageSize=20

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

1번부터 P번까지 P 명의 산타들이 크리스마스 이브를 준비하던 중, 산타의 주요 수송수단인 루돌프가 반란을 일으켰습니다. 루돌프는 산타들을 박치기하여 산타의 선물 배달을 방해하려고 합니다. 산타들은 루돌프를 잡아서 크리스마스를 구해야 합니다!

(1) 게임판의 구성

• 게임판은 N×N 크기의 격자로 이루어져 있습니다. 각 위치는 (r,c)의 형태로 표현되며, 아래로 갈수록 r이 증가, 오른쪽으로 갈수록 c가 증가합니다. 좌상단은 (1,1)입니다.
• 게임은 총 M 개의 턴에 걸쳐 진행되며 매 턴마다 루돌프와 산타들이 한 번씩 움직입니다. 루돌프가 한 번 움직인 뒤, 1번 산타부터 P번 산타까지 순서대로 움직이게 됩니다. 이때 기절해있거나 격자 밖으로 빠져나가 게임에서 탈락한 산타들은 움직일 수 없습니다.
• 게임판에서 두 칸 (r1,c1), (r2,c2) 사이의 거리는 (r1−r2)2+(c1−c2)2으로 계산됩니다.

(2) 루돌프의 움직임

• 루돌프는 가장 가까운 산타를 향해 1칸 돌진합니다. 단, 게임에서 탈락하지 않은 산타 중 가장 가까운 산타를 선택해야 합니다.
• 만약 가장 가까운 산타가 2명 이상이라면, r 좌표가 큰 산타를 향해 돌진합니다. r이 동일한 경우, c 좌표가 큰 산타를 향해 돌진합니다.
• 루돌프는 상하좌우, 대각선을 포함한 인접한 8방향 중 하나로 돌진할 수 있습니다. (편의상 인접한 대각선 방향으로 전진하는 것도 1칸 전진하는 것이라 생각합니다.) 가장 우선순위가 높은 산타를 향해 8방향 중 가장 가까워지는 방향으로 한 칸 돌진합니다.

(3) 산타의 움직임

• 산타는 1번부터 P번까지 순서대로 움직입니다.
• 기절했거나 이미 게임에서 탈락한 산타는 움직일 수 없습니다.
• 산타는 루돌프에게 거리가 가장 가까워지는 방향으로 1칸 이동합니다.
• 산타는 다른 산타가 있는 칸이나 게임판 밖으로는 움직일 수 없습니다.
• 움직일 수 있는 칸이 없다면 산타는 움직이지 않습니다.
• 움직일 수 있는 칸이 있더라도 만약 루돌프로부터 가까워질 수 있는 방법이 없다면 산타는 움직이지 않습니다.
• 산타는 상하좌우로 인접한 4방향 중 한 곳으로 움직일 수 있습니다. 이때 가장 가까워질 수 있는 방향이 여러 개라면, 상우하좌 우선순위에 맞춰 움직입니다.

(4) 충돌

• 산타와 루돌프가 같은 칸에 있게 되면 충돌이 발생합니다.
• 루돌프가 움직여서 충돌이 일어난 경우, 해당 산타는 C만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 루돌프가 이동해온 방향으로 C 칸 만큼 밀려나게 됩니다.
• 산타가 움직여서 충돌이 일어난 경우, 해당 산타는 D만큼의 점수를 얻게 됩니다. 이와 동시에 산타는 자신이 이동해온 반대 방향으로 D 칸 만큼 밀려나게 됩니다.
• 밀려나는 것은 포물선 모양을 그리며 밀려나는 것이기 때문에 이동하는 도중에 충돌이 일어나지는 않고 정확히 원하는 위치에 도달하게 됩니다.
• 만약 밀려난 위치가 게임판 밖이라면 산타는 게임에서 탈락됩니다.
• 만약 밀려난 칸에 다른 산타가 있는 경우 상호작용이 발생합니다.

(5) 상호작용

• 루돌프와의 충돌 후 산타는 포물선의 궤적으로 이동하여 착지하게 되는 칸에서만 상호작용이 발생할 수 있습니다.
• 산타는 충돌 후 착지하게 되는 칸에 다른 산타가 있다면 그 산타는 1칸 해당 방향으로 밀려나게 됩니다. 그 옆에 산타가 있다면 연쇄적으로 1칸씩 밀려나는 것을 반복하게 됩니다. 게임판 밖으로 밀려나오게 된 산타의 경우 게임에서 탈락됩니다.

(6) 기절

• 산타는 루돌프와의 충돌 후 기절을 하게 됩니다. 현재가 k번째 턴이었다면, (k+1)번째 턴까지 기절하게 되어 (k+2)번째 턴부터 다시 정상상태가 됩니다.
• 기절한 산타는 움직일 수 없게 됩니다. 단, 기절한 도중 충돌이나 상호작용으로 인해 밀려날 수는 있습니다.
• 루돌프는 기절한 산타를 돌진 대상으로 선택할 수 있습니다.

(7) 게임 종료

• M 번의 턴에 걸쳐 루돌프, 산타가 순서대로 움직인 이후 게임이 종료됩니다.
• 만약 P 명의 산타가 모두 게임에서 탈락하게 된다면 그 즉시 게임이 종료됩니다.
• 매 턴 이후 아직 탈락하지 않은 산타들에게는 1점씩을 추가로 부여합니다.

게임이 끝났을 때 각 산타가 얻은 최종 점수를 구하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 N, M, P, C, D가 공백을 사이에 두고 주어집니다.

다음 줄에는 루돌프의 초기 위치 (Rr,Rc) 가 주어집니다.

다음 P 개의 줄에 걸쳐서 산타의 번호 Pn과 초기 위치 (Sr,Sc)가 공백을 사이에 두고 주어집니다.

처음 산타와 루돌프의 위치는 겹쳐져 주어지지 않음을 가정해도 좋습니다.

• N: 게임판의 크기 (3≤N≤50)
• M: 게임 턴 수 (1≤M≤1000)
• P: 산타의 수 (1≤P≤30)
• C: 루돌프의 힘 (1≤C≤N)
• D: 산타의 힘 (1≤D≤N)
• Pn: 산타의 번호 (1≤Pn≤P)
• (Rr,Rc): 루돌프의 초기 위치 (1≤Rr,Rc≤N)
• (Sr,Sc): 산타의 초기 위치 (1≤Sr,Sc≤N

출력 형식

게임이 끝났을 때 각 산타가 얻은 최종 점수를 1번부터 P번까지 순서대로 공백을 사이에 두고 출력합니다.

풀이

문제의 길이로만 봐도 조건이 까다로운 것을 알 수 있다

내 단점은 항상 조건 하나를 놓친다는 것..

단점 보완을 위해 전략을 하나 짰다

❤️‍🔥코테 준비 전략❤️‍🔥

1. 문제를 온전히 이해하자
   • 모든 조건 손으로 적어가며 정리
   • 예시가 주어지면 완벽히 이해하자
2. 복작한 로직이라면 손으로 먼저 코딩하자
   • 머릿속에 떠오른 아이디어를 바로 구현하지 않기
   • 순서대로 손으로 표현하면서 조건 생각하기
   • 예외 찾기
3. 테케 돌리기전 마지막 점검해보기
   • 틀린 테스트 케이스에 빠져 숲을 못보게 될 가능성 농후
   • 문제를 다시 읽고 빠진 조건을 확인하자

아이디어

순서대로 하나하나 구현하면 되는 문제

같은 날 치뤄졌던 오전 문제 왕실의 기사대결 와 핵심 챌린지가 비슷하다

연쇄적으로 이동이 일어난다는 것

연쇄적으로 이동이 일어나면 큐를 이용하는 것이 편하다

해야 할 일은 다음과 같다

1. 맵 구성
2. 루돌프 이동 - 충돌
3. 산타 이동 - 충돌
4. 점수 획득

맵 구성

필요한 자료구조를 정리해 보자

1. 루돌프의 위치 저장
2. 산타의 위치, 점수, 탈락 상태, 기절 상태
3. 게임 보드의 상태
4. 탈락한 산타를 저장

산타가 양의 정수로 표현되니 루돌프는 -1로 표현한다

산타의 정보는 해시를 이용해 저장한다

<aside> 💡 산타의 정보 = {산타 번호 : [산타 위치, 점수, 기절 상태, 탈락 여부] }

</aside>

입력 좌표가 1부터 시작하기 때문에 헷갈리지 않게 인덱스를 조정하여 저장한다

N, M, P, C, D = map(int, input().split())
r_x, r_y = map(int, input().split())

init_santas = [list(map(int, input().split())) for _ in range(P)]
board = [[0] * N for _ in range(N)]

# 빈칸 : 0, 루돌프: -1, 산타: 1~P
board[r_x - 1][r_y - 1] = -1
r_x = r_x - 1
r_y = r_y - 1

# 산타의 상태를 저장하는 해시 : {산타 번호 : [산타 위치, 점수, 기절 상태, 탈락 여부]}
santa_info = {i: [0, 0, 0, False] for i in range(1, P + 1)}

for idx, x, y in init_santas:
    board[x - 1][y - 1] = idx
    santa_info[idx][0] = [x - 1, y - 1]

remove_santa = []  # 탈락한 산타를 저장

루돌프 이동

1. 가까운 산타 선정
2. 방향 결정
3. 이동
4. 충돌

가까운 산타는 탈락하지 않은 산타의 거리를 모두 계산해, 최소인 산타를 결정한다

이때, 거리가 같은 산타가 여럿 존재할 수 있다

우선순위는 [행> 열] 이기 때문에 이상태로 정렬하면 됨

방향 결정은 x, y좌표의 크기에 따라 결정하도록 했다

따로 함수로 빼서 하는게 마음의 안정이 옴

이동했을 때 그 곳이 빈칸이면 그대로, 충돌이면 충돌 함수를 호출한다

    # 1. 루돌프 이동
    temp = []
    max_distance = 0

    # 1.1 가장 가까운 산타 선택
    for idx in range(1, P + 1):
        # 탈락한 산타는 제외
        if santa_info[idx][3]:
            temp.append(100000000) # 바로 여기!!!
            continue
        x, y = santa_info[idx][0][0], santa_info[idx][0][1]
        temp.append(cal_distance(x, y, r_x, r_y))

    min_distance = min(temp)

    # 가까운 위치에 있는 산타 후보
    candi_santa = [idx + 1 for idx, i in enumerate(temp) if i == min_distance]
    candi_santa = [[santa_info[i][0], i] for i in candi_santa]

    candi_santa.sort(reverse=True)  # r,c가 큰 순으로 우선순위 정리

    select_santa = candi_santa[0][-1]  # 선택된 산타

    # 1.2 산타로 향하는 방향 계산
    rudolf_d = select_direction(santa_info[select_santa][0], [r_x, r_y])

    # 1.3 방향으로 루돌프 이동
    board[r_x][r_y] = 0
    r_x = r_x + dx[rudolf_d]
    r_y = r_y + dy[rudolf_d]

    # 1.4 루돌프 이동으로 인한 충돌
    if board[r_x][r_y] > 0:
        crash("rudolf", rudolf_d, board[r_x][r_y], r_x, r_y)
        board[r_x][r_y] = -1
    # 충돌 없이 이동
    else:
        board[r_x][r_y] = -1

문제를 다 풀고 제출 했는데 94%에서 갑자기 틀리더라

테스트케이스 53번..

진짜 모르겠어서 코드트리에 토론하기에 물어봤는데 노력해보라는 답변을 받았다

오기로 알아내려고 난리 쳐서 겨우 알아냄

정말 사소한 값때문에 틀렸다 시험장가서도 이러면 안되는데 ㅠㅠ

교수님이 이런 곳에는 말도안되게 큰 값을 써라 했는데 내가 간과함

충돌

충돌은 2개의 경우의 수가 있다

산타가 충돌한 경우, 루돌프가 충돌한 경우

다른 점은 방향, 점수 획득

이외는 동일하기 때문에 하나의 함수 안에서 해결 하도록 했다

산타의 기절은 충돌할때 2를 더한 후, 턴이 지날 때마다 1씩 줄어들게 설계했다

상호작용이 일어나면 큐에 넣어 연쇄적으로 이동이 일어나도록 함

처음에 어디서 실수 했는지 자꾸 보드 상태가 이상하게 되길래 아예 새로운 보드를 만들어 다시 설정하도록 해버렸다

def crash(who, dir, santa_id, x, y):
    global board
    score = D if who == "santa" else C
    santa_info[santa_id][1] += score    # 충돌 점수 획득
    santa_info[santa_id][2] = 2      # 산타 기절

    # 산타가 이동한 반대 방향으로 이동
    if who == "santa":
        if dir %2 == 0: # 상 하
            dir = dir_ver[abs(dir_ver.index(dir)-1)]

        else:   # 좌 우
            dir = dir_hori[abs(dir_hori.index(dir)-1)]

    q = deque()
    q.append([santa_id, x, y, dir, score])
    
    while q:
        moving, x, y, dir, score = q.popleft()
        nx = x + dx[dir]*score
        ny = y + dy[dir]*score

        # 산타가 탈락한 경우
        if not is_board(nx, ny):
            santa_info[moving][3] = True        # 탈락 상태 on
            remove_santa.append(moving)         # 탈락 산타 리스트 추가
            break

        # 상호작용이 시작
        if board[nx][ny] >0 and board[nx][ny] != moving:
            q.append([board[nx][ny], nx, ny, dir, 1])
            santa_info[moving][0] = [nx, ny]

        # 상호작용이 필요 없는 경우
        else:
            santa_info[moving][0] = [nx, ny]
            break

    board = [[0] * N for _ in range(N)]
    for key, value in santa_info.items():
        if not value[3]:
            x, y = value[0][0], value[0][1]
            board[x][y] = key

    board[r_x][r_y] = -1
    return

산타 이동

산타는 동시이동이 아닌 순서 이동이기 때문에 순서대로 옮기면 된다

기절 했거나 탈락한 산타는 무시한다

루돌프와 다르게 산타는 4방향으로만 움직이고, 산타와 가까워지지 않으면 움직이지 않는다

def santa_move(info, key):
    x, y = info[0], info[1]
    cur_dis = cal_distance(x, y, r_x, r_y)
    candi = []
    # 산타 움직일 방향(우선순위: 상-우-하-좌)
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        # 이동한 경우 게임 밖 / 다른 산타가 존재: 이동 x
        if not is_board(nx, ny) or board[nx][ny] > 0:
            continue
        next_dis = cal_distance(nx, ny, r_x, r_y)
        # 루돌프와의 거리가 줄어듦
        if cur_dis > next_dis:
            cur_dis = next_dis
            candi.append([nx, ny, d])
    # 이동할 수 없음
    if len(candi) == 0: return
    nx, ny, dir = candi.pop()
    # 2.1 산타 이동으로 인한 충돌
    # if board[nx][ny] == -1:
    if [r_x, r_y] == [nx, ny]:
        crash("santa", dir, key, nx, ny)

    else:
        santa_info[key][0] = [nx, ny]
        board[x][y] = 0
        board[nx][ny] = key

코드

from collections import deque

def print_board(board):
    for line in board:
        print(line)

def is_board(x, y):
    return 0 <= x < N and 0 <= y < N

def cal_distance(x1, y1, x2, y2):
    return pow(x1 - x2, 2) + pow(y1 - y2, 2)

def select_direction(santa, rudolf):
    # 방향이 위쪽
    if santa[0] - rudolf[0] < 0:
        if santa[1] == rudolf[1]:
            return 0  # 상
        elif santa[1] < rudolf[1]:
            return 6  # 상좌
        else:
            return 4  # 상우
    # 방향이 아래쪽
    elif santa[0] - rudolf[0] > 0:
        if santa[1] == rudolf[1]:
            return 2  # 하
        elif santa[1] < rudolf[1]:
            return 7  # 하좌
        else:
            return 5  # 하우
    # 방향이 좌/우
    else:
        if santa[1] < rudolf[1]:
            return 3  # 좌
        else:
            return 1  # 우

def crash(who, dir, santa_id, x, y):
    global board
    score = D if who == "santa" else C
    santa_info[santa_id][1] += score    # 충돌 점수 획득
    santa_info[santa_id][2] = 2      # 산타 기절
    # 산타가 이동한 반대 방향으로 이동
    if who == "santa":
        # print("산타충돌!!")
        if dir %2 == 0: # 상 하
            dir = dir_ver[abs(dir_ver.index(dir)-1)]

        else:   # 좌 우
            dir = dir_hori[abs(dir_hori.index(dir)-1)]

    q = deque()
    q.append([santa_id, x, y, dir, score])
    while q:
        moving, x, y, dir, score = q.popleft()
        nx = x + dx[dir]*score
        ny = y + dy[dir]*score

        # 산타가 탈락한 경우
        if not is_board(nx, ny):
            santa_info[moving][3] = True    # 탈락 상태 on
            remove_santa.append(moving)        # 탈락 산타 리스트 추가
            break

        # 상호작용이 시작
        if board[nx][ny] >0 and board[nx][ny] != moving:
            # print(f"{board[nx][ny]}가 존재")
            q.append([board[nx][ny], nx, ny, dir, 1])
            santa_info[moving][0] = [nx, ny]

        # 상호작용이 필요 없는 경우
        else:
            santa_info[moving][0] = [nx, ny]
            break

    board = [[0] * N for _ in range(N)]
    for key, value in santa_info.items():
        if not value[3]:
            x, y = value[0][0], value[0][1]
            board[x][y] = key

    board[r_x][r_y] = -1
    return

def santa_move(info, key):
    x, y = info[0], info[1]
    cur_dis = cal_distance(x, y, r_x, r_y)
    candi = []
    # 산타 움직일 방향(우선순위: 상-우-하-좌)
    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        # 이동한 경우 게임 밖 / 다른 산타가 존재: 이동 x
        if not is_board(nx, ny) or board[nx][ny] > 0:
            continue
        next_dis = cal_distance(nx, ny, r_x, r_y)
        # 루돌프와의 거리가 줄어듦
        if cur_dis > next_dis:
            cur_dis = next_dis
            candi.append([nx, ny, d])
    # 이동할 수 없음
    if len(candi) == 0: return
    nx, ny, dir = candi.pop()
    # 2.1 산타 이동으로 인한 충돌
    # if board[nx][ny] == -1:
    if [r_x, r_y] == [nx, ny]:
        crash("santa", dir, key, nx, ny)

    else:
        santa_info[key][0] = [nx, ny]
        board[x][y] = 0
        board[nx][ny] = key

#  상:0, 우:1, 하:2, 좌:3, 상우:4, 하우:5, 상좌:6, 하좌:7
dx = [-1, 0, 1, 0, -1, 1, -1, 1]
dy = [0, 1, 0, -1, 1, 1, -1, -1]

dir_santa = [[0,2], [3,1]]
dir_ver = [0, 2]    # 상, 하, 짝수
dir_hori = [3, 1]   # 좌, 우, 홀수

N, M, P, C, D = map(int, input().split())
r_x, r_y = map(int, input().split())

init_santas = [list(map(int, input().split())) for _ in range(P)]
board = [[0] * N for _ in range(N)]

# 빈칸 : 0, 루돌프: -1, 산타: 1~P
board[r_x - 1][r_y - 1] = -1
r_x = r_x - 1
r_y = r_y - 1
# 산타의 상태를 저장하는 해시 : {산타 번호 : [산타 위치, 점수, 기절 상태, 탈락 여부]}
santa_info = {i: [0, 0, 0, False] for i in range(1, P + 1)}

for idx, x, y in init_santas:
    board[x - 1][y - 1] = idx
    santa_info[idx][0] = [x - 1, y - 1]

remove_santa = []  # 탈락한 산타를 저장

# M번 동안 턴 명령
for _ in range(1, M+1):
    # P명의 산타가 탈락한 경우
    if len(remove_santa) == P:
        break
    # 기절 상태 산타 확인
    for key, value in santa_info.items():
        if value[2] > 0 and not value[3]:
            santa_info[key][2] -= 1

    # 1. 루돌프 이동
    temp = []
    max_distance = 0

    # 1.1 가장 가까운 산타 선택
    for idx in range(1, P + 1):
        # 탈락한 산타는 제외
        if santa_info[idx][3]:
            temp.append(100000000)
            continue
        x, y = santa_info[idx][0][0], santa_info[idx][0][1]
        temp.append(cal_distance(x, y, r_x, r_y))

    min_distance = min(temp)

    # 가까운 위치에 있는 산타 후보
    candi_santa = [idx + 1 for idx, i in enumerate(temp) if i == min_distance]
    candi_santa = [[santa_info[i][0], i] for i in candi_santa]

    candi_santa.sort(reverse=True)  # r,c가 큰 순으로 우선순위 정리

    select_santa = candi_santa[0][-1]  # 선택된 산타

    # 1.2 산타로 향하는 방향 계산
    rudolf_d = select_direction(santa_info[select_santa][0], [r_x, r_y])

    # 1.3 방향으로 루돌프 이동
    board[r_x][r_y] = 0
    r_x = r_x + dx[rudolf_d]
    r_y = r_y + dy[rudolf_d]

    # 1.4 루돌프 이동으로 인한 충돌
    if board[r_x][r_y] > 0:
        crash("rudolf", rudolf_d, board[r_x][r_y], r_x, r_y)
        board[r_x][r_y] = -1
    # 충돌 없이 이동
    else:
        board[r_x][r_y] = -1

    # 2. 산타 이동
    for key, value in santa_info.items():
        # 움직일 수 없는 산타(기절 했거나, 탈락한 경우) : continue
        # 아무리 움직여도 루돌프와 가까워 지지 않는 경우: continue
        if santa_info[key][3] or santa_info[key][2] > 0: continue
        santa_move(santa_info[key][0], key)

    # 탈락하지 않은 산타 +1점
    for idx in range(1, P+1):
        if not santa_info[idx][3]:
            santa_info[idx][1] += 1

score = [str(value[1]) for value in santa_info.values()]
print(' '.join(score))

---

자꾸 프린트 구간에서 틀렸다고 해서 저렇게 해버렸다

print(score[i], end = “ ”)

를 써도 될듯