[코드트리] 왕실기사의 대결 - 큐 이용 / Python(파이썬)

지난 번에 푼 https://harami.tistory.com/63  은 기사들의 좌표를 모두 저장하고 연쇄적인 처리를 했기 때문에 아주아주 비효율적인 풀이였다. 이번엔 큐를 이용하여 다시 문제를 풀어주었다. 풀이 시작!

기사 이동

기사에게 주어지는 정보 r, c, w, h, k를 저장 하면서 탈락 여부와 누적 데미지를 저장해야한다. 각 기사마다 가진 정보이기 때문에 해시를 이용해 저장한다.

#               x,   y,   크기, 체력, 받은 데미지, 탈락여부
sirs = {idx+1:[[x-1, y-1], [h, w],  k,      0,        False] for idx, (x, y, h, w, k) in enumerate(sirs)}

기사는 총 q개의 명령을 수행하며 명령을 받은 기사가 체스판에 없는 경우, 즉 탈락한 경우 명령을 수행 할 수 없다.

명령을 받은 기사는 di 방향으로 한칸 이동할 수 있고, 이웃한 기사들 모두가 한방향씩 연쇄적으로 밀린다. 이때 이동하는 기사중 하나라도 벽에 부딪히면 움직일 수 없다.

연쇄 작용은 큐를 이용해 구현한다. 기사가 한칸 이동하고, 기사가 차지하는 모든 좌표가 하나라도 벽에 부딪한다면 모든것이 무효가 되도록 한다.

 

    q = deque()
    q.append(id)

    check = set()
    check.add(id)

    # 이동이 완료 된 후, 데미지 적용하기 때문에 따로 저장
    demage = [0]* (n+1)
    # print(demage)
    while q:
        sid = q.popleft()
        print('이동하는 기사:', sid)
        [x, y], [h, w] = sirs[sid][0], sirs[sid][1]

        nx = x + dx[di]
        ny = y + dy[di]
        print(f"{x, y} ->{nx, ny} ")
        for i in range(nx, nx + h):
            for j in range(ny, ny + w):
                print(i, j)
                # 벽이 발견되면 모두 취소
                if not is_board(i,j) or board[i][j] == 2:
                    print('벽')
                    return
                # 함정이 있는 만큼 데미지
                if board[i][j] == 1:
                    demage[sid] += 1

주의할 점!! 데미지는 모든 기사의 움직임이 끝난후 입는 다는 점. 연쇄적으로 바로 처리하다가 움직여야 할 기사를 없애는 불상사가 없도록 꼭 확인해야함.

기사는 첫 x좌표가 (r, r + h-1), y 좌표가 (c, c+w-1)로 이루어진 직사가형 모양이기 때문에 반복문을 이용해서 모든 칸안에서 벽과 함정을 조사한다.

 

    q = deque()
    q.append(id)

    check = set()
    check.add(id)

    # 이동이 완료 된 후, 데미지 적용하기 때문에 따로 저장
    demage = [0]* (n+1)
    # print(demage)
    while q:
        sid = q.popleft()
        print('이동하는 기사:', sid)
        [x, y], [h, w] = sirs[sid][0], sirs[sid][1]

        nx = x + dx[di]
        ny = y + dy[di]
        print(f"{x, y} ->{nx, ny} ")
        for i in range(nx, nx + h):
            for j in range(ny, ny + w):
                print(i, j)
                # 벽이 발견되면 모두 취소
                if not is_board(i,j) or board[i][j] == 2:
                    print('벽')
                    return
                # 함정이 있는 만큼 데미지
                if board[i][j] == 1:
                    demage[sid] += 1

set을 이용해 이미 이동을 완료한 기사를 저장한다. 이동 이후에 인접한 경우 한번더 옮기지 않도록한다.

이동기사(A)가 다른 기사(B)와 부딪혀 밀리는 조건은 A의 왼쪽 상단 모서리가 B의 오른쪽 하단안에 있는 것, B의 오른쪽 하단 모서리가 A의 왼쪽 상단 모서리에 있어야한다. 하나의 격자가 겹치는 최소의 조건이 된다.

이 조건을 만족한다면 겹치게 된 경우이기 때문에 큐에 삽입하여 한칸 이동시킨다.

데결 데미지

모든 기사의 이동이 완료되면, 데미지를 입힌다. 미리 데미지를 저장해놓은 후, 이동이 끝난다음 기사 정보를 저장해둔 해시에 결과값을 넣어주어야함.

 

# 명령 받은 기사의 데미지 0으로
    demage[id] = 0
    # for key, value in sirs.items():
    for key in check:
        print(f"{key}기사 {demage[key]}데미지")
        sirs[key][3] += demage[key]
        sirs[key][2] -= demage[key]
        # 받은 데미지가 체력보다 크면 탈락
        # if sirs[key][2] > sirs[key][3]:
        if sirs[key][2] <= 0:
            sirs[key][4] = True
        else:
            [sx, sy] = sirs[key][0]
            sirs[key][0] = [sx + dx[di], sy + dy[di]]

저장 된 체력에 데미지를 준 후, 체력이 0이하로 떨어지면 체스 밖으로 탈락 시킨다. 저장된 x,y값은 한칸 이동한 값으로 바꿔주면 모든 기사의 이동, 데미지 까지 완료된다.

코드

 

l, n, q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(l)]
# r, c, h, w, k
sirs = [list(map(int, input().split())) for _ in range(n)]
# i, d
orders = [list(map(int, input().split()))for _ in range(q)]
#               x,   y,   크기, 체력, 받은 데미지, 탈락여부
sirs = {idx+1:[[x-1, y-1], [h, w],  k,      0,        False] for idx, (x, y, h, w, k) in enumerate(sirs)}
print(sirs)
# 격자 내부 확인
def is_board(x, y):
    return 0 <= x < l and 0<= y < l

def printboard(board):
    for line in board:
        print(line)
# 0:위, 1:오, 2:아, 3:왼
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

from collections import deque
def move_sir(id, di):
    # [x, y] = sirs[id][0]
    q = deque()
    q.append(id)

    check = set()
    check.add(id)

    # 이동이 완료 된 후, 데미지 적용하기 때문에 따로 저장
    demage = [0]* (n+1)
    # print(demage)
    while q:
        sid = q.popleft()
        print('이동하는 기사:', sid)
        [x, y], [h, w] = sirs[sid][0], sirs[sid][1]

        nx = x + dx[di]
        ny = y + dy[di]
        print(f"{x, y} ->{nx, ny} ")
        for i in range(nx, nx + h):
            for j in range(ny, ny + w):
                print(i, j)
                # 벽이 발견되면 모두 취소
                if not is_board(i,j) or board[i][j] == 2:
                    print('벽')
                    return
                # 함정이 있는 만큼 데미지
                if board[i][j] == 1:
                    demage[sid] += 1

        # 이동 했을때 밀리는 기사 확인
        for ss in sirs.keys():
            # 이미 이동하는 기사 넘어가기
            if ss in check or sirs[ss][-1]: continue
            [sx, sy], [sh, sw] = sirs[ss][0], sirs[ss][1]
            # 왼쪽 상단 모서리가 다른 격자 내부에 존재 / 오른쪽 하단 모서리가 다른 격자 내부에 존재
            if (nx <= sx + sh + -1 and ny <= sy + sw -1) and (sx <= nx + h-1 and sy <= ny + w -1):
                q.append(ss)
                check.add(ss)

    # 명령 받은 기사의 데미지 0으로
    demage[id] = 0
    # for key, value in sirs.items():
    for key in check:
        print(f"{key}기사 {demage[key]}데미지")
        sirs[key][3] += demage[key]
        sirs[key][2] -= demage[key]
        # 받은 데미지가 체력보다 크면 탈락
        # if sirs[key][2] > sirs[key][3]:
        if sirs[key][2] <= 0:
            sirs[key][4] = True
        else:
            [sx, sy] = sirs[key][0]
            sirs[key][0] = [sx + dx[di], sy + dy[di]]
    print(sirs)




    print(x, y)
# q 개의 명령을 수행
for id, di in orders:
    print()
    print(f"{id}기사가 {di}방향으로 이동")
    # 탈락한 기사 명령 수행 불가
    if sirs[id][4]:
        print('탈락 기사 명령 무시')
        continue

    # 기사 이동
    move_sir(id, di)
    print(sirs)

output = [value[3] for value in sirs.values() if not value[4]]
print(output)
print(sum(output))

큐를 이용

좌표 계산

확실히 수행 시간이 개선 된 것을 볼 수 있다. 

그래도 시험장에서 아무 생각도 안든다면, 그때 생각나는걸 구현 하는게 최고다!!!