[코드트리] 왕실의 기사대결 / 파이썬(python)

문제

https://www.codetree.ai/problems/royal-knight-duel/description

왕실의 기사들은 L×L 크기의 체스판 위에서 대결을 준비하고 있습니다. 체스판의 왼쪽 상단은 (1,1)로 시작하며, 각 칸은 빈칸, 함정, 또는 벽으로 구성되어 있습니다. 체스판 밖도 벽으로 간주합니다.

왕실의 기사들은 자신의 마력으로 상대방을 밀쳐낼 수 있습니다. 각 기사의 초기위치는 (r,c)로 주어지며, 그들은 방패를 들고 있기 때문에 (r,c)를 좌측 상단으로 하며 h(높이)×w(너비) 크기의 직사각형 형태를 띄고 있습니다. 각 기사의 체력은 k로 주어집니다.

(1) 기사 이동

왕에게 명령을 받은 기사는 상하좌우 중 하나로 한 칸 이동할 수 있습니다. 이때 만약 이동하려는 위치에 다른 기사가 있다면 그 기사도 함께 연쇄적으로 한 칸 밀려나게 됩니다. 그 옆에 또 기사가 있다면 연쇄적으로 한 칸씩 밀리게 됩니다. 하지만 만약 기사가 이동하려는 방향의 끝에 벽이 있다면 모든 기사는 이동할 수 없게 됩니다. 또, 체스판에서 사라진 기사에게 명령을 내리면 아무런 반응이 없게 됩니다.

(2) 대결 대미지

명령을 받은 기사가 다른 기사를 밀치게 되면, 밀려난 기사들은 피해를 입게 됩니다. 이때 각 기사들은 해당 기사가 이동한 곳에서 w×h 직사각형 내에 놓여 있는 함정의 수만큼만 피해를 입게 됩니다. 각 기사마다 피해를 받은 만큼 체력이 깎이게 되며, 현재 체력 이상의 대미지를 받을 경우 기사는 체스판에서 사라지게 됩니다. 단, 명령을 받은 기사는 피해를 입지 않으며, 기사들은 모두 밀린 이후에 대미지를 입게 됩니다. 밀렸더라도 밀쳐진 위치에 함정이 전혀 없다면 그 기사는 피해를 전혀 입지 않게 됨에 유의합니다.

Q 번에 걸쳐 왕의 명령이 주어졌을 때, Q 번의 대결이 모두 끝난 후 생존한 기사들이 총 받은 대미지의 합을 출력하는 프로그램을 작성해보세요.

입력형식

첫 번째 줄에 L, N, Q가 공백을 사이에 두고 주어집니다.

다음 L 개의 줄에 걸쳐서 L×L 크기의 체스판에 대한 정보가 주어집니다.

• 0이라면 빈칸을 의미합니다.
• 1이라면 함정을 의미합니다.
• 2라면 벽을 의미합니다.

다음 N 개의 줄에 걸쳐서 초기 기사들의 정보가 주어집니다. 이 정보는 (r,c,h,w,k) 순으로 주어지며, 이는 기사의 처음 위치는 (r,c)를 좌측 상단 꼭지점으로 하며 세로 길이가 h, 가로 길이가 w인 직사각형 형태를 띄고 있으며 초기 체력이 k라는 것을 의미합니다. 입력은 1번 기사부터 N번 기사까지 순서대로 정보가 주어집니다.

단, 처음 주어지는 기사들의 위치는 기사들끼리 서로 겹쳐져 있지 않습니다. 또한 기사와 벽은 겹쳐서 주어지지 않습니다.

다음 Q 개의 줄에 걸쳐 왕의 명령에 대한 정보가 주어집니다. 이 정보는 (i,d) 형태로 주어지며 이는 i번 기사에게 방향 d로 한 칸 이동하라는 명령임을 뜻합니다. i는 1 이상 N 이하의 값을 갖으며, 이미 사라진 기사 번호가 주어질 수도 있음에 유의합니다. d는 0, 1, 2, 3 중에 하나이며 각각 위쪽, 오른쪽, 아래쪽, 왼쪽 방향을 의미합니다.

• L: 체스판의 크기 (3≤L≤40)
• N: 기사의 수 (1≤N≤30)
• Q: 명령의 수 (1≤Q≤100)
• k: 기사의 체력 (1≤k≤100)

출력 형식

Q 개의 명령이 진행된 이후, 생존한 기사들이 총 받은 대미지의 합을 출력합니다.

풀이

아이디어

23년 하반기 오전 삼성 코딩테스트 문제..

서류 붙을지도 모르고 공부 열심히 안하다가 벼락치기로 공부하고 시험장에 갔다

4시간동안 2문제를 푸는 시험에 무조건 하나만 풀자는 마음가짐으로 임한다

1번문제는 그동안 연습했던 bfs구현 문제인게 눈에 보였다

2번문제.. 보자마자 이건 다음을 기약하기루 함

사실 30분만 더 있었다면 풀었을 것 같다..

거의 다 풀었다고 생각함!!! …

시험장을 나와서 울적했지만 홀가분했던 것 같음..

4시간동안 풀었지만 결국 풀지 못했던 슬픈 문제.. 풀이를 시작합니다~

먼저, 그때 생각했던 아이디어 그대로 유지하면서 풀고 싶었다

문제에서 나뉘듯이 해야할 일은 크게 2가지

1. 기사 이동
2. 대결 데미지

연쇄적으로 밀려나는 기사들을 어떻게 조사할지 엄청 고민이 됐다

시험장에서 생각난 것은 기사들의 좌표를 구해서 밀자! 였음

기사들의 정보는 해시를 이용해 저장한다

sirs = {i+1:[] for i in range(N)}
# [로봇의 위치, h, w], k
for idx, sir in enumerate(fighter):
    r,c,h,w,k = sir[0]-1, sir[1]-1, sir[2], sir[3], sir[4]
    sirs[idx+1].append([r, c, h, w])
    sirs[idx+1].append(k)

기사 이동

기사 이동 작업에서 해야할 일은 다음과 같다

• 이미 체스판에서 삭제된 기사의 이동명령 무시
• 기사의 모든 좌표를 구한다
• set을 이용해 이동하는 기사를 저장
• 큐를 이용해 밀려나야 할 기사를 확인
  • 한칸 밀었을 때 벽이 존재 / 격자 바깥 → 명령 종료
  • 이웃이면서 아직 밀지 않은 기사인 경우 → 큐에 삽입
• 좌표를 이동

def get_xy(arr, temp):
    r,c,h,w = arr[0], arr[1], arr[2], arr[3]
    for x in range(r, r+h):
        for y in range(c, c+w):
                temp.append([x, y])
    return temp 
     
def is_board(x, y):
    return 0 <= x < L and 0 <= y < L
    
def move_sirs(i, d):
    # 체스판에서 삭제된 기사 이동 명령
    if i not in sirs.keys():
        return []
    
    # 현존하는 기사들의 좌표 저장
    states = {}
    for key in sirs.keys():
        temp = []
        states[key] = get_xy(sirs[key][0], temp)
    
    # 이동 명령을 받은 기사
    q = deque()
    get_xy(sirs[i][0], q)
    moved_sir.add(i)

    while q:
        x, y = q.popleft()
        nx = x + dx[d]
        ny = y + dy[d]

        # 이동한 곳이 격자 밖인 경우
        if not is_board(nx, ny):    return []
        
        for key, value in states.items():
            # 같이 밀릴 기사가 있고, 아직 밀리지 않은 기사인 경우
            if [nx, ny] in value and key not in moved_sir:
                moved_sir.add(key)
                get_xy(sirs[key][0], q)
        
        # 밀린 곳이 벽인 경우
        if board[nx][ny] == 2:
            return []
        else:
            moved_sir.add(i)
            
    # 밀릴 기사들의 좌표를 이동
    for idx in moved_sir:
        sirs[idx][0][0] += dx[d]
        sirs[idx][0][1] += dy[d]

    return moved_sir

대결 데미지

데미지를 입을때 고려해야하는 조건

• 이동 명령을 받은 기사는 타격 없음
• 데미지를 주는 함정의 개수가 가진 k보다 큰 경우 체스판에서 사라짐

다 풀고 계속 테스트 케이스 19에서 에러가 났다

내가 실수 한 부분은 체스판에서 사라진 기사의 데미지를 계속 저장해 계산할 때 포함되었기 때문

출력은 현재 체스판에 살아있는 기사가 입은 데미지의 총합이기 때문에 사라진 기사의 데미지는 삭제해줘야한다

→ 이건 데미지를 관리하는 해시를 따로 만들어 해결함

정리하고 나니 별거 없지만 이거 알아내기 위해 인고의 시간을 버텨야 했다는 것…

하지만 해냈죠!

def get_damege(moved_sir, id):
    if not moved_sir:
        return
    states = {}
    # 기사 범위 좌표 구하기
    for idx in moved_sir:
        temp = []
        states[idx] = get_xy(sirs[idx][0], temp)
    
    # 좌표를 돌면서 함정을 지나면 데미지 입기
    for key, value in states.items():
        cnt = 0
        for x, y in value:
            # 함정의 개수 세기
            if board[x][y] == 1:
                cnt += 1
        # 남은 피 <= 입는 데미지: 데미지 없앰 & 체스판에서 없애기
                
        # 19번에서 에러가 난 이유 : 이미 피를 -시켰는데 죽어버린 경우까지 포함해버림
        # damege를 따로 관리로 해결 (damege를 따로 관리하면서 원래의 피도 깎아줘야함)
        if  cnt >= sirs[key][1]:
            damege[key] = 0
            del sirs[key]
        else:
            sirs[key][1] -= cnt
            damege[key] += cnt

결

과적으로는 풀이 성공

하지만 수행 시간 부문에서 최악의 풀이라고 생각한다

좌표 계산을 여러번 하기 때문

하지만 시험자의 내가 이렇게 풀고 있었기 때문에 그 풀이를 완료하고자 그대로 풀어봤다..

나중에 컴팩트 풀이를 다시 해봐야겠다..

코드

from collections import deque

L, N, Q = map(int, input().split())

board = [list(map(int, input().split())) for _ in range(L)]
fighter = [list(map(int, input().split())) for _ in range(N)]

sirs = {i+1:[] for i in range(N)}
order = [list(map(int, input().split())) for _ in range(Q)]
def get_xy(arr, temp):
    r,c,h,w = arr[0], arr[1], arr[2], arr[3]
    for x in range(r, r+h):
        for y in range(c, c+w):
                temp.append([x, y])
    return temp  

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


def move_sirs(i, d):
    # 체스판에서 삭제된 기사 이동 명령
    if i not in sirs.keys():
        return []
    
    # 현존하는 기사들의 좌표 저장
    states = {}
    for key in sirs.keys():
        temp = []
        states[key] = get_xy(sirs[key][0], temp)
    
    # 이동 명령을 받은 기사
    q = deque()
    get_xy(sirs[i][0], q)
    moved_sir.add(i)


    while q:
        x, y = q.popleft()
        nx = x + dx[d]
        ny = y + dy[d]

        # 이동한 곳이 격자 밖인 경우
        if not is_board(nx, ny):
            return []
        
        for key, value in states.items():
            # 같이 밀릴 기사가 있고, 아직 밀리지 않은 기사인 경우
            if [nx, ny] in value and key not in moved_sir:
                moved_sir.add(key)
                get_xy(sirs[key][0], q)
        
        # 밀린 곳이 벽인 경우
        if board[nx][ny] == 2:
            return []
        else:
            moved_sir.add(i)
    # 밀릴 기사들의 좌표를 이동
    for idx in moved_sir:
        sirs[idx][0][0] += dx[d]
        sirs[idx][0][1] += dy[d]


    return moved_sir

def get_damege(moved_sir, id):
    if not moved_sir:
        return
    states = {}
    # 기사 범위 좌표 구하기
    for idx in moved_sir:
        temp = []
        states[idx] = get_xy(sirs[idx][0], temp)
    
    # 좌표를 돌면서 함정을 지나면 데미지 입기
    for key, value in states.items():
        cnt = 0
        for x, y in value:
            # 함정의 개수 세기
            if board[x][y] == 1:
                cnt += 1
        # 남은 피 <= 입는 데미지: 데미지 없앰 & 체스판에서 없애기
        # if sirs[key][1] - cnt <= 0:
                
        # 19번에서 에러가 난 이유 : 이미 피를 -시켰는데 죽어버린 경우까지 포함해버림
        # damege를 따로 관리로 해결 (damege를 따로 관리하면서 원래의 피도 깎아줘야함)
        if  cnt >= sirs[key][1]:
            damege[key] = 0
            del sirs[key]
        else:
            sirs[key][1] -= cnt
            damege[key] += cnt

# 로봇 해시로 저장
# [로봇의 위치, h, w], k
for idx, sir in enumerate(fighter):
    r,c,h,w,k = sir[0]-1, sir[1]-1, sir[2], sir[3], sir[4]
    sirs[idx+1].append([r, c, h, w])
    sirs[idx+1].append(k)
print(sirs)

 # 0:위, 1:오른, 2:아래, 3:왼
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

damege = {i+1:0 for i in range(N)}  # 데미지를 저장

for i, d in order:
    moved_sir = set()    # 이동 한 기사

    # 1. 기사 이동
    moved_sir = move_sirs(i, d)

    # 명령을 받은 기사는 데미지x
    if moved_sir:
        moved_sir.remove(i)

    #2. 데미지 입기
    get_damege(moved_sir, i)

# 명령이 끝난 후 살아남은 기사의 데미지 합
print(sum(damege.values()))