문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

www.acmicpc.net/problem/17135

  • 입력

첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다.

  • 출력

첫째 줄에 경로의 개수를 출력한다. 이 값은 int 범위이다.

최종 코드

초반에 꽤 오래 헤멨다.

  1. arr를 deepcopy 해주지 않는 실수를 저질렀다.
  2. 같은 적이 여러 궁수에게 공격당할 수 있다는 점을 간과했다.

역시 문제를 꼼꼼히 읽고 실수를 줄이는 게 중요하다는 생각이 든다.

import sys
from collections import deque
from itertools import combinations
import copy

def bfs(s1, s2, s3, arr):
    ret = 0

    # 적들이 한 칸씩 전진한다
    for i in range(n):
        # 같은 적이 여러 궁수에게 공격당할 수 있으므로 우선 공격당한 적을 tmp에 저장한다
        tmp = []
        # 세 명의 궁수가 각자 활을 쏜다
        for s in [s1, s2, s3]:
            q = deque()
            q.append([n - i, s, 0])
            visit = [[False] * m for _ in range(n - i)]
            flag = True
            while q and flag:
                x, y, cnt = q.popleft()
                # 밑으로는 이동할 필요가 없으므로 왼쪽-위-오른쪽만 탐색한다
                for dx, dy in zip([0, -1, 0], [-1, 0, 1]):
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < n - i and 0 <= ny < m and visit[nx][ny] == False:
                        # 다음 칸에 적이 있는 경우
                        if arr[nx][ny] == 1:
                            # 적을 처음 죽이는 경우
                            if [nx, ny] not in tmp:
                                # tmp에 적의 위치를 넣고 ret 값 +1
                                tmp.append([nx, ny])
                                ret += 1
                                flag = False
                            break
                        visit[nx][ny] = True
                        # 공격 거리를 넘지 않는 한에서 탐색 진행
                        if cnt + 1 < d:
                            q.append([nx, ny, cnt + 1])
        # 공격당한 적 처리
        for x, y in tmp:
            arr[x][y] = 0
    return ret

n, m, d = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
com = combinations([i for i in range(m)], 3)
res = 0

for c in com:
    res = max(res, bfs(c[0], c[1], c[2], copy.deepcopy(arr)))

print(res)

Enhanced

분명 다른 방법도 존재할 것 같아서 찾아봤다.

나는 적을 bfs를 통해 찾았는데 굳이 bfs를 이용하지 않아도 되는 문제였다. 적의 위치를 리스트에 담아놓고 |r1-r2| + |c1-c2| 계산을 통해 한 번에 거리를 구할 수 있었다. 그렇게 구한 거리를 통해 적들을 거리가 짧은 순 - 열이 작은 순으로 정렬하여 문제를 해결할 수 있었다.

자세한 건 코드의 주석 참고!

import sys
from itertools import combinations

def go(archer):
    ret = 0
    # kill: 3명의 궁수와 적들의 거리, 적의 위치를 저장
    kill = [[], [], []]
    visit = [[0] * m for _ in range(n)]

    for x, y in enemy:
        for i in range(3):
            # (적과의 거리, 적의 좌표 x, y) 저장
            kill[i].append((abs(n - x) + abs(archer[i] - y), x, y))
    for i in range(3):
        # 1. 거리 2. 열 순으로 정렬
        kill[i].sort(key = lambda x: (x[0], x[2]))

    # 적들이 한 칸씩 전진한다
    for i in range(n):
        # 세 명의 궁수가 각자 활을 쏜다
        for j in range(3):
            # 행이 이미 궁수를 넘어간 적은 삭제
            while kill[j] and kill[j][0][1] > (n - 1 - i):
                kill[j].pop(0)
            # 사정거리 안에 있는 경우
            while kill[j] and kill[j][0][0] <= d + i:
                dist, x, y = kill[j].pop(0)
                # 행이 이미 궁수를 넘어갔거나 이미 죽은 적이라면 계속 탐색
                if x > (n - 1 - i) or 0 < visit[x][y] <= i:
                    continue
                # 처음 적을 죽이는 경우 ret + 1
                elif visit[x][y] == 0:
                    visit[x][y] = i + 1
                    ret += 1
                # 중복되는 적을 죽이는 경우엔 그냥 break
                break

    return ret

n, m, d = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
com = combinations([i for i in range(m)], 3)
enemy = []
res = 0

# 적의 위치 저장
for i in range(n):
    for j in range(m):
        if arr[i][j] == 1:
            enemy.append([i, j])

for c in com:
    res = max(res, go(c))

print(res)

참고 사이트