[삼성 SW 역량테스트 2023 하반기 오전 1번 문제] 왕실의 기사 대결

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

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

 

정신 똑바로 차리면 쉽게 풀 수 있는 문제. 

쉽게 해결하였다. 

 

처음에 check_trap 부분에서 if k ==0: break를 한번만 해주어서 40%쯤에 테스트 케이스 오류를 받음 

금방 오류를 찾아서 다행이다. 

---

나의 풀이 

import sys
sys.stdin = open('input.txt', 'r')

def direction(d):
    if d == 0:
        dx,dy=-1,0
    elif d == 1:
        dx,dy=0,1
    elif d == 2:
        dx,dy=1,0
    elif d == 3:
        dx,dy=0,-1
    return dx,dy

def person_move(pid, dx,dy):
    global people_board, person_loc
    r,c,h,w,k = person_loc[pid]
    for i in range(h):
        for j in range(w):
            people_board[r+i][c+j] = 0
    for i in range(h):
        for j in range(w):
            people_board[r+i+dx][c+j+dy] = -pid
    person_loc[pid] = [r+dx,c+dy,h,w,k]

def check_wall(pid,dx,dy):
    r,c,h,w,k = person_loc[pid]
    for i in range(h):
        for j in range(w):
            if board[r+i+dx][c+j+dy] == 2:  # 벽이 하나라도 있으면 
                return False
    return True

# 연쇄반응 
def Interaction(pid, dx,dy, new_pid, move_person_list):  # 재귀함수 
    # 그 다음에 벽이 있는지 확인 
    # 기사 움직일 수 있는지 없는지 확인 
    r,c,h,w,k = person_loc[new_pid]
    
    can_move=True
    # 이동할 곳에 벽이 있는지 없는지 부터 확인 
    if not check_wall(new_pid,dx,dy):
        return False, move_person_list
    
    # 이동할 위치에 다른 기사가 있는지 확인 
    for i in range(h):
        for j in range(w):
            if people_board[r+i+dx][c+j+dy] != 0 and people_board[r+i+dx][c+j+dy] != -new_pid:    # 다른 기사가 있으면 
                can_move, move_person_list = Interaction(new_pid, dx,dy, -people_board[r+i+dx][c+j+dy], move_person_list)
                if not can_move:    # 
                    # # 연쇄작용이 안된다는 것을 알았을때, 연쇄작용으로 움직인 다른 기사를 다시 되돌려야함 
                    # temp_person_loc[pid] = person_loc[pid]
                    return can_move, move_person_list
                
    # 움직일 수 있으면 
    if can_move:
        if new_pid not in move_person_list:
            move_person_list.append(new_pid)
            temp_person_loc[new_pid] = [r+dx, c+dy, h,w,k]
    
    return can_move, move_person_list

def check_trap(pid):
    global scores
    r,c,h,w,k = temp_person_loc[pid]
    for i in range(h):
        for j in range(w):
            if board[r+i][c+j] == 1:    # 함정이 있으면 
                k-=1
                scores[pid] += 1
                if k == 0:
                    break 
        if k == 0:
            break 
        
    if k == 0:
        del person_loc[pid]
        for i in range(h):
            for j in range(w):
                people_board[r+i][c+j]=0
    else:
        person_loc[pid] = [r,c,h,w,k]
    
    
    

# 이동할 위치에 다른 기사가 있는지 확인 
def check_person(pid,dx,dy):
    can_move = True
    move_person_list=[]
    for i in range(h):
        for j in range(w):
            if people_board[r+i+dx][c+j+dy] != 0 and people_board[r+i+dx][c+j+dy] != -pid:    # 다른 기사가 있으면 
                # 연쇄작용을 확인하고 최종적으로 이동 가능하면 True 
                can_move,move_person_list = Interaction(pid, dx,dy, -people_board[r+i+dx][c+j+dy], move_person_list)
                if not can_move:
                    # # 연쇄작용이 안된다는 것을 알았을때, 연쇄작용으로 움직인 다른 기사를 다시 되돌려야함 
                    # temp_person_loc[pid] = person_loc[pid]
                    return can_move
    
    for pid in move_person_list:
        person_move(pid, dx,dy)
        check_trap(pid)
        
    return can_move


# 체스판 밖도 벽으로 간주합니다.
if __name__=="__main__":
    # L:체스판의 크기, N:기사의 수, Q:명령의 수 
    L,N,Q=map(int, input().split()) 
    # L×L 크기의 체스판에 대한 정보
    board = [[2]*(L+2)] + [[2] + list(map(int, input().split())) + [2] for _ in range(L)] + [[2]*(L+2)]
    people_board = [[0]*(L+2) for _ in range(L+2)]
    # 초기 기사들의 정보
    person_loc = {}
    temp_person_loc = {}
    for pid in range(1,N+1):
        r,c,h,w,k=map(int, input().split()) # 기사의 처음 위치: (r,c), h,w: 세로, 가로, k: 초기체력
        person_loc[pid] = [r,c,h,w,k]
        temp_person_loc[pid] = [r,c,h,w,k]
        for i in range(h):
            for j in range(w):
                people_board[r+i][c+j] = -pid
    
    scores = [0]*(N+1)
    # Q개의 왕의 명령 
    for _ in range(Q):
        pid,d = map(int, input().split()) # i번의 기사에게 방향 d로 한칸 이동하라는 명령 
        if person_loc.get(pid)==None:
            continue
        r,c,h,w,k = person_loc[pid]
        dx,dy = direction(d)
        
        # 기사 이동, 다른 기사들 위치 확인하고 연쇄반응일으키는지 확인, 연쇄 반응 안일으키거나 일으켜도 이동가능하면 이동 
        can_move=True
        # 이동할 곳에 벽이 있는지 없는지 부터 확인 
        can_move = check_wall(pid,dx,dy)
        
        # 이동할 곳에 벽이 없어서 이동 가능하면, 이동할 곳에 다른 기사가 있는지 확인 
        if can_move:
            can_move = check_person(pid,dx,dy)

        # 연쇄작용 다 확인했는데 이동 가능하면 최종적으로 이동 
        if can_move:
            can_move = person_move(pid,dx,dy)
    
    answer = 0
    for pid in person_loc:
        answer += scores[pid]
    
    print(answer)

 

 

---

그러나 해설 방법이 훨씬 간단하다. 해설 처럼 푸는 방법에 익숙해져야겠다. 

포인트는 deque를 사용하여 연쇄작용을 구현하였다는 것이다. 

from collections import deque

import sys
sys.stdin = open('input.txt', 'r')


dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 범위 
def in_range(nx,ny,h,w):
    return 1<=nx<=L+1-h and 1<=ny<=L+1-w

# 움직임을 시도해봅니다.
def try_movement(idx, dir):
    q = deque()

    # 초기화 작업입니다.
    for pid in range(1, N + 1):     # 1번 기사부터 N번 기사까지 
        dmg[pid] = 0                # 받은 데미지 0으로 초기화 
        is_moved[pid] = False       # 움직임 False로 초기화 
        nr[pid] = r[pid]            # temporal r을 일단 현재 위치 r로 초기화
        nc[pid] = c[pid]            # temporal r을 일단 현재 위치 r로 초기화

    q.append(idx)
    is_moved[idx] = True            # 모체 기사를 기준으로 움직임 시작 

    while q:                        # 현재 시작 기사를 시작으로 딸려오는 연쇄작용이 일어나는 다음 기사들이 append로 쌓음
        x = q.popleft()

        nr[x] += dx[dir]            # 새로운, 움직일 위치 
        nc[x] += dy[dir]

        # 경계를 벗어나는지 체크합니다.
        if not in_range(nr[x],nc[x],h[x],w[x]):
            return False        # 범위를 벗어나는 움직임이면 못 움직임

        # 대상 기사가 함정이나 벽과 충돌하는지 검사합니다.
        for i in range(nr[x], nr[x] + h[x]):
            for j in range(nc[x], nc[x] + w[x]):
                if info[i][j] == 1:     # 함정이면 
                    dmg[x] += 1         # 데미지 축적 
                if info[i][j] == 2:     # 벽이 하나라도 있으면 
                    return False        # 못 움직임 

        # 대상 기사가 다른 기사와 충돌하는 경우, 해당 조각도 같이 이동합니다.
        for pid in range(1, N + 1):
            if is_moved[pid] or k[pid] <= 0:    # 이미 움직였거나, 체력이 0이하라 체스판에 없는 경우 
                continue                        # 안움직임 
            # 체스판 범위에 벗어나면 못 움직임
            if r[pid] > nr[x] + h[x] - 1 or nr[x] > r[pid] + h[pid] - 1:
                continue
            if c[pid] > nc[x] + w[x] - 1 or nc[x] > c[pid] + w[pid] - 1:
                continue

            is_moved[pid] = True
            # 연쇄적으로 움직이게 하기 위해 큐를 사용 
            q.append(pid)       # 그 다음 움직여야 할 기사 pid         

    # return False 없이 여기까지 무사히 도달했으면 
    dmg[idx] = 0        
    return True


# 특정 조각을 지정된 방향으로 이동시키는 함수입니다.
def move_piece(idx, move_dir):
    if k[idx] <= 0:             # 체력이 0이하라 체스판에 없는 경우 
        return                  # 끝 

    # 이동이 가능한 경우,
    if try_movement(idx, move_dir): # idx 기사가 움직일 수 있는지 확인 
        for pid in range(1, N + 1): # 기사들의 실제 위치와 체력을 업데이트한다.
            r[pid] = nr[pid]
            c[pid] = nc[pid]
            k[pid] -= dmg[pid]


if __name__=="__main__":
    # L:체스판의 크기, N:기사의 수, Q:명령의 수 
    L, N, Q = map(int, input().split())
    MAX_N = 31  # 최대 기사 수 
    MAX_L = 41  # 최대 체스판 크기 
    info = [[0 for _ in range(MAX_L)] for _ in range(MAX_L)]    # 최대크기 체스판
    bef_k = [0 for _ in range(MAX_N)]   # 최대 개수 기사들의 초기 체력  
    r = [0 for _ in range(MAX_N)]       # 처음 기사 위치 행 
    c = [0 for _ in range(MAX_N)]       # 처음 기사 위치 열 
    h = [0 for _ in range(MAX_N)]       # 기사의 범위 세로 h 
    w = [0 for _ in range(MAX_N)]       # 기사의 범위 가로 w 
    k = [0 for _ in range(MAX_N)]       # 기사의 체력 
    nr = [0 for _ in range(MAX_N)]      # 기사가 움직일 위치 행 
    nc = [0 for _ in range(MAX_N)]      # 기사가 움질일 위치 열 
    dmg = [0 for _ in range(MAX_N)]     # 기사가 받은 데미지 
    is_moved = [False for _ in range(MAX_N)]    # 움직임 체크 

    for i in range(1, L + 1):
        info[i][1:] = map(int, input().split())
    
    # 기사 번호에 따른 각각의 정보를 리스트에 담는다?
    for pid in range(1, N + 1):
        r[pid], c[pid], h[pid], w[pid], k[pid] = map(int, input().split())
        bef_k[pid] = k[pid]

    # Q개의 왕의 명령 
    for _ in range(Q):
        idx, d = map(int, input().split())  # i번의 기사에게 방향 d로 한칸 이동하라는 명령 
        move_piece(idx, d)

    # 결과를 계산하고 출력합니다.
    ans = sum([bef_k[i] - k[i] for i in range(1, N + 1) if k[i] > 0])
    print(ans)

 

 

해설 정답을 보고 다시 푼 나의 코드 

from collections import deque

import sys
sys.stdin = open('input.txt', 'r')

moves = [(-1,0),(0,1),(1,0),(0,-1)]

# 범위 
def in_range(nx,ny,h,w):
    return 1<=nx<=L+1-h and 1<=ny<=L+1-w

# 움직임을 시도해봅니다.
def try_movement(idx, dir):
    q = deque()
    q.append(idx)
    
    # 초기화 작업입니다.
    for pid in range(1, N + 1):     # 1번 기사부터 N번 기사까지 
        dmg[pid] = 0                # 받은 데미지 0으로 초기화 
        is_moved[pid] = False       # 움직임 False로 초기화 
        nr[pid] = r[pid]            # 새로운 위치 r을 일단 현재 위치 r로 초기화
        nc[pid] = c[pid]            # 새로운 위치 c을 일단 현재 위치 c로 초기화

    is_moved[idx] = True            # 현재 기사를 기준으로 움직임 시작 
    
    while q:
        x = q.popleft()

        nr[x] += moves[dir][0]            # 새로운, 움직일 위치 
        nc[x] += moves[dir][1]

        # 경계를 벗어나는지 체크합니다.
        if not in_range(nr[x],nc[x],h[x],w[x]):
            return False        # 범위를 벗어나는 움직임이면 못 움직임

        # 함정이거나 벽인지 확인 
        for i in range(nr[x], nr[x] + h[x]):
            for j in range(nc[x], nc[x] + w[x]):
                if board[i][j] == 1:     # 함정이면 
                    dmg[x] += 1         # 데미지 축적 
                if board[i][j] == 2:     # 벽이 하나라도 있으면 
                    return False        # 못 움직임 

        # 대상 기사가 다른 기사와 충돌하는 경우, 해당 조각도 같이 이동합니다.
        for pid in range(1, N + 1):
            if is_moved[pid] or k[pid] <= 0:    # 이미 움직였거나, 체력이 0이하라 체스판에 없는 경우 
                continue                        # 안움직임 
            # pid 기사위치가 현재 기사의 새 위치의 범위 밖에 있으면 안옴직임 또는
            # 현재 기사의 새 위치가 pid 기사 범위 밖이면 안움직임 
            if (r[pid] > nr[x] + h[x] - 1) or (nr[x] > r[pid] + h[pid] - 1):
                continue
            if (c[pid] > nc[x] + w[x] - 1) or (nc[x] > c[pid] + w[pid] - 1):
                continue

            is_moved[pid] = True
            # 연쇄적으로 움직이게 하기 위해 큐를 사용 
            q.append(pid)       # 그 다음 움직여야 할 기사 pid         

    # return False 없이 여기까지 무사히 도달했으면 
    dmg[idx] = 0        
    return True


# 특정 조각을 지정된 방향으로 이동시키는 함수입니다.
def move_piece(idx, move_dir):
    if k[idx] <= 0:             # 체력이 0이하라 체스판에 없는 경우 
        return                  # 끝 

    # 이동이 가능한 경우,
    if try_movement(idx, move_dir): # idx 기사가 움직일 수 있는지 확인 
        for pid in range(1, N + 1): # 기사들의 실제 위치와 체력을 업데이트한다.
            r[pid] = nr[pid]
            c[pid] = nc[pid]
            k[pid] -= dmg[pid]


if __name__=="__main__":
    # L:체스판의 크기, N:기사의 수, Q:명령의 수 
    L, N, Q = map(int, input().split())
    MAX_N = 31  # 최대 기사 수 
    MAX_L = 41  # 최대 체스판 크기 
    
    board = [[2]*(L+2)] + [[2] + list(map(int, input().split())) + [2] for _ in range(L)] + [[2]*(L+2)]
    
    init_k = [0 for _ in range(MAX_N)]   # 최대 개수 기사들의 초기 체력  
    r = [0]*MAX_N       # 처음 기사 위치 행 
    c = [0]*MAX_N      # 처음 기사 위치 열 
    h = [0]*MAX_N       # 기사의 범위 세로 h 
    w = [0]*MAX_N       # 기사의 범위 가로 w 
    k = [0]*MAX_N       # 기사의 체력 
    nr = [0]*MAX_N      # 기사가 움직일 위치 행 
    nc = [0]*MAX_N      # 기사가 움질일 위치 열 
    dmg = [0]*MAX_N    # 기사가 받은 데미지 
    is_moved = [False]*MAX_N    # 움직임 체크 
    
    # 기사 번호에 따른 각각의 정보를 리스트에 담는다?
    for pid in range(1, N + 1):
        r[pid], c[pid], h[pid], w[pid], k[pid] = map(int, input().split())
        init_k[pid] = k[pid]

    # Q개의 왕의 명령 
    for _ in range(Q):
        idx, d = map(int, input().split())  # i번의 기사에게 방향 d로 한칸 이동하라는 명령 
        move_piece(idx, d)

    # 결과를 계산하고 출력합니다.
    ans = sum([init_k[i] - k[i] for i in range(1, N + 1) if k[i] > 0])
    print(ans)