[백준][브루트포스] 캐슬 디펜스

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/17135

 

내가 작성한 코드

import sys
from collections import deque, defaultdict
from itertools import combinations

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

def get_data():
    read = sys.stdin.readline

    N, M, D = map(int, read().rstrip().split())
    enermies = []
    for r in range(N):
        crnt = list(map(int, read().rstrip().split()))
        for c in range(M):
            if crnt[c] == 1:
                enermies.append((r,c))
    available = [(N, c) for c in range(M)]

    return N, M, D, enermies, available

def distance(x, y):
    return abs(x[0] - y[0]) + abs(x[1] - y[1])

def attack(towers, enermies, N, M, D):
    died = []
    for tower in towers:
        q = deque([(tower, 0)])
        visitied = defaultdict(bool)
        visitied[tower] = True

        while q:
            crnt, cost = q.popleft()

            if crnt in enermies:
                died.append(crnt)
                break

            for d in dir:
                nw_crnt = tuple(sum(x) for x in zip(crnt, d))

                if 0 <= nw_crnt[0] < N and 0 <= nw_crnt[1] < M and cost + 1 <= D and not visitied[nw_crnt]:
                    visitied[nw_crnt] = True
                    q.append((nw_crnt, cost+1))

    return set(died)

def move(enermies, N):
    nw_enermies = []
    for r, c in enermies:
        if r+1 < N:
            nw_enermies.append((r+1, c))
    return nw_enermies



N, M, D, enermies, available = get_data()
mx_died = 0
for towers in combinations(available, 3):
    crnt_enermies = enermies[:]
    total_died = 0
    while crnt_enermies:
        crnt_died = attack(towers, crnt_enermies, N, M, D)
        total_died += len(crnt_died)
        for dead in crnt_died:
            crnt_enermies.remove(dead)
        crnt_enermies = move(crnt_enermies, N)
    mx_died = max(mx_died, total_died)

print(mx_died)

• 조합 (combinations)
  
  • 궁수를 배치할 수 있는 모든 경우의 수
• 공격 (attack)
  • 적이 모두 사라질 때까지
  • 궁수의 위치에서 BFS로 가장 가까운 적 찾기
  • 집합(set)으로 중복을 고려하여 적 제거
• 이동 (move)
  • 성에 도착하는 것을 고려
  • 아래로 한 칸 이동

 

다른 사람이 작성한 코드

import sys
from itertools import combinations
from heapq import heappop, heappush

n, m, d = map(int, sys.stdin.readline().rstrip().split())
MAP = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
arr = []

castle_pos = [i for i in range(m)]
archer_cases = tuple(combinations(castle_pos, 3))
answer = 0

def get_enemy_count():
    global arr
    cnt = 0
    
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 1: cnt += 1
    
    return cnt

def attack_enemy(archer_case_index):
    global arr
    remove_list = []
    attacked = [[False for _ in range(m)] for _ in range(n)]
    cnt = 0

    for archer_pos in archer_cases[archer_case_index]:
        pq = [] # [거리, x, y]를 우선순위 큐에 삽입

        for i in range(n-1, -1, -1):
            for j in range(m):
                if arr[i][j] == 1:
                    diff = abs(n-i) + abs(archer_pos-j)
                    if diff <= d:
                        heappush(pq, [diff, j, i])

        if pq:  
            _, x, y = heappop(pq)
            remove_list.append([y, x])
    
    for y, x in remove_list:
        if not attacked[y][x]:
            attacked[y][x] = True
            cnt += 1
            arr[y][x] = 0
    
    return cnt

def move_enemy():
    global arr
    arr[-1] = [0 for _ in range(m)]

    for i in range(-1, -n, -1):
        arr[i] = arr[i-1]
    
    arr[0] = [0 for _ in range(m)]

def simulation(archer_case_index):
    cnt = 0

    while get_enemy_count() != 0:
        cnt += attack_enemy(archer_case_index)
        move_enemy()
        
    return cnt

for i in range(len(archer_cases)):
    arr = [[MAP[i][j] for j in range(m)] for i in range(n)]
    cnt = simulation(i)
    if answer < cnt: answer = cnt

print(answer)

• 우선순위 큐를 이용한 BFS
  
  • (거리, x, y)로 거리와 가장 왼쪽의 적을 선택하는 방식

https://velog.io/@study-dev347/%EB%B0%B1%EC%A4%80-17135-%EC%BA%90%EC%8A%AC-%EB%94%94%ED%8E%9C%EC%8A%A4

[백준 17135] 캐슬 디펜스(Python)

기억해야할 것

• 문제 파악
  
  • 처음에 성의 위치가 어디인지 작성되지 않아서 해매었음
  • 모든 격자에 성을 배치하는 방식으로 작성했었음