[BOJ] 17135. 캐슬 디펜스(Python) / DFS + BFS

17135번: 캐슬 디펜스

# 1h 58m 소요

• 사용 알고리즘 : DFS + BFS / 자료구조 : 큐, 최소 힙(우선순위 큐)
• 오랜만에 이렇게 온갖 알고리즘이 섞인 문제를 풀었다. 장장 2시간여의 긴 여정이었다. 두 번째 푸는 문제라 나름 자신했지만, 처음에 코드 설계하고 다 풀고 디버깅하느라 시간이 좀 걸려서 아쉬웠다.. 한 번에 고려했어야 하는데!
• 일단 아래 코드는 죽일 적을 최소 힙 큐에 담으면서 가장 높은 우선순위의 적을 뽑아 사용하도록 했다.
• 시간, 메모리 면에서 매우 오래걸리는 코드라 또 다른 두 가지 방법으로 구현해봤다. 
• 풀이 설명이 빡세서 이번에는 그냥 주석으로 설명을 대신한다.

 

일단, 최소 힙을 사용한 파이썬 코드는 다음과 같다.

---

from sys import stdin
input = stdin.readline
from collections import deque
from heapq import heappush, heappop

# 상 좌 우
dr = (-1, 0, 0)
dc = (0, -1, 1)

# 궁수가 있는 열
def killEnemy(pos, A):
    enemyLst = set()   # 죽일 적의 후보 위치 리스트 - 중복 제거를 위해 set 사용
    check = [[-1] * M for _ in range(N)]        # 공유하기 위함
    for col in pos:			# col열에 배치된 궁수마다 따로 bfs 시행
        pq = []             # 궁수마다 초기화
        if A[N-1][col]:     # 탐색 시작 위치에 적 있으면 바로 우선순위 큐에 담기
            heappush(pq, (1, col, N-1))
        check[N-1][col] = col
        Q = deque([(N-1, col, 1)])
        while Q:
            r, c, dis = Q.popleft()
            if dis == D:     # 거리 공격 제한 거리 D 넘으면
                break
            for d in range(3):
                nr = r + dr[d]
                nc = c + dc[d]
                if not (0 <= nr < N and 0 <= nc < M) or check[nr][nc] == col:
                    continue
                check[nr][nc] = col
                Q.append((nr, nc, dis+1))
                if A[nr][nc]:   # 적이 있는 곳이라면 우선순위 큐에 담기
                    heappush(pq, (dis+1, nc, nr))   # 적의 후보(우선순위 : 거리 > 열 > 행 순)
        
        if pq:	  # 죽일 수 있는 적이 있는 경우에만
            dis, ec, er = heappop(pq)
            enemyLst.add((er, ec))     # col열에 위치한 궁수가 죽일 적의 위치 리스트에 담기

    return enemyLst

# 궁수의 공격
def attack(pos):
    global maxKill
    A = [x[:] for x in raw]     # 궁수 배치 후 사용할 맵 A에 복사
    killCnt = 0                 # 죽인 적의 수
    
    for _ in range(N):
        enemyLst = killEnemy(pos, A)    # 죽일 적의 후보 위치 리스트

        # 적 죽이기
        for er, ec in enemyLst:     # 타겟 적 죽이기
            # print((er, ec))
            A[er][ec] = 0
            killCnt += 1
        
        # 적 한 칸씩 아래로 이동
        A.pop()
        A.insert(0, [0] * M)

    maxKill = max(maxKill, killCnt)     # 최댓값 갱신

# 재귀로 조합 구현 = > 3명의 궁수 성에 배치
def posArcher(depth, k):
    if depth == 3:
        attack(castle)
        return

    for i in range(k, M):
        castle.append(i)
        posArcher(depth+1, i+1)
        castle.pop()

# main
N, M, D = map(int, input().split())
raw = [list(map(int, input().split())) for _ in range(N)]

maxKill = 0
castle = []
posArcher(0, 0)
print(maxKill)

---

• 시간 : 516ms / 메모리 : 130360kb
• 시간, 메모리가 남들보다 많이 든 코드라 아쉽다. 덱과 힙을 사용해서 더 뭔가 복잡해보이지만 큰 틀에서의 문제 흐름은 같다. 뭔가 개선이 필요하다.. 다음 코드는 시간 복잡도를 절반 이상으로, 공간 복잡도도 꽤 줄인 개선된 코드이다. 
• 2가지 방법으로 짜봤는데, 하나는 조합을 dfs 재귀로 구현한 것, 하나는 itertools combination 라이브러리를 사용한 것이다.
• 달라진 것은 방향 델타 좌표를 (좌 > 상 > 우) 순으로 만들어둬서 우선순위 높은 부분부터 탐색해 적을 만나면 바로 죽일 적의 후보 리스트에 담는 것이다. 
• 지금 아래에 보이는 코드는 방법 2고,
• 방법 1부분을 열 때는 방법 2부분을 주석처리하고 코드 맨 윗 부분 라이브러리 호출한 부분을 주석처리 하고 보면 된다.  

 

힙을 사용하지 않고 적을 만나면 flag가 True로 바뀌며 바로 bfs를 탈출할 수 있도록 구현한 코드다. 확실히 깔끔하다.

---

from sys import stdin
input = stdin.readline
from collections import deque
from itertools import combinations

# 상 좌 우
dr = (0, -1, 0)
dc = (-1, 0, 1)

# 궁수가 있는 열
def killEnemy(pos, A):
    enemyLst = set()   # 죽일 적의 후보 위치 리스트 - 중복 제거를 위해 set 사용
    
    check = [[-1] * M for _ in range(N)]        # 궁수별 적 찾는 visited를 공유하기 위함
    for col in pos:
        if A[N-1][col]:     # 탐색 시작 위치에 적이 있는 경우 가장 가까운 적임
            enemyLst.add((N-1, col))
            continue

        check[N-1][col] = col
        Q = deque([(N-1, col, 1)])      # (위치, 거리)
        flag = False
        while Q:
            r, c, dis = Q.popleft()
            if dis == D:     # 거리 공격 제한 거리 D 넘으면
                break
            for d in range(3):
                nr = r + dr[d]
                nc = c + dc[d]
                if not (0 <= nr < N and 0 <= nc < M) or check[nr][nc] == col:
                    continue
                check[nr][nc] = col
                Q.append((nr, nc, dis+1))
                if A[nr][nc]:       # 가장 처음 만난 적을 enemyLst에 담기
                    enemyLst.add((nr, nc))
                    flag = True
                    break
            if flag:
                break
    return enemyLst

# 궁수의 공격
def attack(pos):
    global maxKill
    A = [x[:] for x in raw]     # 궁수 배치 후 사용할 맵 A에 복사
    killCnt = 0                 # 죽인 적의 수
    
    for _ in range(N):
        enemyLst = killEnemy(pos, A)    # 죽일 후보 적의 위치 리스트

        # 적 죽이기
        for er, ec in enemyLst:     # 타겟 적 죽이기
            A[er][ec] = 0
            killCnt += 1
        
        # 적 한 칸씩 아래로 이동
        A.pop()
        A.insert(0, [0] * M)

    maxKill = max(maxKill, killCnt)     # 최댓값 갱신

# (방법 1) 재귀로 조합 구현 => 3명의 궁수 배치 경우의 수 구하기
# def posArcher(depth, k):
#     global maxKill
#     if maxKill == enemyCnt:     # 이미 다 죽였으면
#         return

#     if depth == 3:
#         attack(castle)
#         return

#     for i in range(k, M):
#         castle.append(i)
#         posArcher(depth+1, i+1)
#         castle.pop()

# main
N, M, D = map(int, input().split())
enemyCnt = 0        # 맵에 있는 모든 적의 수
raw = []
for r in range(N):
    raw.append(list(map(int, input().split())))
    for c in range(M):
        if raw[r][c]:
            enemyCnt += 1
maxKill = 0

# 방법 1 - dfs 재귀로 조합 구현
# castle = []
# posArcher(0, 0)

# 방법 2 - itertools 패키지의 combination 라이브러리 사용
for comb in combinations(range(M), 3):
    attack(comb)
    if maxKill == enemyCnt:     # 이미 다 죽였으면
        break
print(maxKill)

---

• 시간 : 224ms / 메모리 : 127244kb
• 고찰 : 이제야 좀 성에 찬다 ㅋㅋ 쌩 시뮬레이션이라기보다 DFS + BFS 콤비의 나름대로 재밌지만 또 고통스럽기도 했던 문제였다.ㅎㅎ 점점 시간, 공간 복잡도를 계산하며 푸는데 익숙해지는 것 같다. Keep Going