본문 바로가기

취업과 기본기 튼튼/코딩 테스트 노트

[BOJ] 17135. 캐슬 디펜스

문제

캐슬 디펜스 (https://www.acmicpc.net/problem/17135)

풀이

1. 초기접근

  • 문제조건 해석

    • 판이 주어지고, 각 턴에 따라 판의 형태가 달라진다.

    • 문제에서 이야기 했 듯, 궁수의 위치가 중요하다. 궁수의 위치에 따라, 진행되는 판의 모양이 달라진다.

      • N, M <= 15 로 주어지고, 궁수의 수도 3명으로 제한된다. 완전탐색으로 풀만하다.
      • 최대 nC3 의 조합의 각 경우에 대해 일일이 탐색해야 한다.
    • 여기서 또 핵심이 되는 조건은 다음이다.

      모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.

      거리가 D이하인 가장 가까운 -> BFS다.
      가장 왼쪽에 있는 -> 방향 순서를 고려해줘야 한다.

    • 같은 적이 여러 궁수에게 공격당할 수 있다는 말은, 각 궁수가 없애고자하는 좌표가 겹칠 수 있다는 말이다.

      • 없앨 좌표를 일괄적을 처리해야 한다.
  • 알고리즘

    • 먼저, 각 궁수가 위치할 수 있는 모든 경우를 구한다음, 각 경우를 탐색한다.
      • itertools.combination 을 이용하면 된다.
    • 각 경우에서, 3명의 궁수가 이번 스텝에 없앨 적의 좌표(target) 를 구한다.
      • 좌표의 중복이 허용되므로, set() 을 이용하여 담는다.
    • 없앨 좌표를 일괄적으로 없앤다.
    • 판(board)에서 적들이 한 칸 내려오고, 판에 적이 남았는지 확인한다.
    • 적이 있으면, 다시 위를 반복하고, 없는 경우, 다음 궁수 조합으로 넘어간다.
  • 코드

from itertools import combinations
from copy import deepcopy
from collections import deque
dxs = [0, -1, 0]
dys = [-1, 0, 1]

def enemy_move():
    is_empty = True
    for i in range(n-1, 0, -1):
        for j in range(m):
            board[i][j] = board[i-1][j]
            if board[i][j] == '1':
                is_empty = False
    for j in range(m):
        board[0][j] = '0'
    return is_empty

def bfs(x, y):
    q = deque([(x, y)])
    visited = set([(x, y)])
    step = 1

    while q:
        size = len(q)
        for _ in range(size):
            x, y = q.popleft()
            if board[x][y] == '1':
                return (x, y)
            for dx, dy in zip(dxs, dys):
                nx, ny = x + dx, y + dy
                if nx >= 0 and ny >= 0 and ny < m and (nx, ny) not in visited:
                    q.append((nx, ny))
                    visited.add((nx, ny))
        step += 1
        if step > d:
            return None

n, m, d = list(map(int, input().split()))
board_org = [list(input().split()) for _ in range(n)]
max_kill = 0

for locs in combinations(list(range(m)), 3):
    board = deepcopy(board_org)
    kill = 0

    while True:
        targets = set()
        for loc in locs:
            target = bfs(n-1, loc)
            if target is not None:
                targets.add(target)

        for (x, y) in targets:
            board[x][y] = '0'
            kill += 1

        if enemy_move():
            break

    max_kill = max(max_kill, kill)
print(max_kill)

'취업과 기본기 튼튼 > 코딩 테스트 노트' 카테고리의 다른 글

[BOJ] 5430. AC  (2) 2019.04.22
[BOJ] 2493. 탑  (2) 2019.04.18
[BOJ] 14891. 톱니바퀴  (2) 2019.04.11
[BOJ] 12100. 2048 (Easy)  (2) 2019.04.11
[BOJ] 14499. 주사위 굴리기  (0) 2019.04.11