[백준 17135번] 캐슬 디펜스 (파이썬)

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

17135번: 캐슬 디펜스

문제를 처음 읽고 당황했던 것.

'궁수는 어디다가 배치하지??'

입력값은 빈칸 or 적이라서

궁수는 어디다가 배치하나 했더니

격자아래에 궁수가 배치되었다는 전제.

 

구현할 걸 순서대로 나열하면 이렇습니다.

 

1. 궁수 위치

-->combination으로 나타냈습니다.

이렇게하면 시간초과 뜰 것 같았는데

질문하기의 코드들을 참고해보니

combination써도 되겠다 싶었습니다.

 

2. 궁수가 적을 맞추기

-->BFS로 적을 탐색해서 제거해주기

이 때, 중복이 나올 수 있음에 유의.

 

3. 적을 한칸씩 내려보내기

-->제 스타일상에서는 이 부분이 에러가 많았습니다.

 

*주의할 점

BFS로 탐색할 때

3개만 움직이면 됩니다.

'왜 4번은 구현하지 않았나요?'

어처피 적은 궁수기준으로 앞에 있으니

뒤로 가는 건 굳이 구현할 필요가 없습니다.

구현하면 시간초과가 뜰까봐 구현하지 않았습니다.

그리고 우선순위에 대한 부분입니다.

문제에서

'가장 왼쪽의 적을 제거한다'라고 적혀있습니다.

그래서 처음에는

'왼 오 위'

이 순서대로 구현했으나 오답판정을 받았습니다.

이후 반례들을 참고해보니

'왼 위 오'가 맞았습니다.

왼쪽순대로보면 왼 위 오가 맞긴 하네요.

 

백준 17135번 캐슬 디펜스
from collections import deque
from itertools import combinations
from copy import deepcopy

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

N,M,D=map(int,input().split())
room=[]
person=[]
for i in range(N):
    tmp=list(map(int,input().split()))
    for j in range(M):
        if tmp[j]==1:
            person.append([i,j])
    room.append(tmp)
answer=0

#궁수 조합
co=[i for i in range(M)]
com=combinations(co,3)



for go in com:
    n_p=deepcopy(person)
    cnt=0
    #1 궁수 사격
    #2 병사들 내려옴
    while len(n_p)>0:
        cut=[]
        #1
        for g in go:
            tmp=deque()
            tmp.append([N-1,g,1])
            t_visited=[[False]*M for _ in range(N)]
            t_visited[N-1][g]=True
            while tmp:
                x,y,count=tmp.popleft()

                if [x,y] in n_p and count<=D:
                    cut.append([x,y])
                    break

                if count+1>D:
                    continue
                for d in range(3):
                    nx=x+dx[d]
                    ny=y+dy[d]

                    if nx<0 or nx>=N or ny<0 or ny>=M:
                        continue
                    if t_visited[nx][ny]==True:
                        continue

                    tmp.append([nx,ny,count+1])
        #print(cut)
        for cx,cy in cut:
            #print(cx,cy)
            if [cx,cy] not in n_p:
                continue
            p=n_p.index([cx,cy])
            n_p.pop(p)
            cnt+=1
        #print(n_p,1,cnt)
        #2
        po=[]
        for nx,ny in n_p:
            inde=n_p.index([nx,ny])
            if nx+1>=N:
                po.append([nx,ny])
            else:
                n_p[inde][0]+=1
        for px,py in po:
            inde=n_p.index([px,py])
            n_p.pop(inde)
        #print(n_p,2)
        #print(cnt)
    #print(cnt)
    answer=max(answer,cnt)
print(answer)

pypy3로 제출한 코드입니다.

병사들 내려오는 부분이

다소 복잡하게 되어있습니다.

코드를 보면서 설명하자면

1. 먼저 현재 있는 사람들의 좌표를 받는다.

2. 한칸 내리고 범위를 벗어나면 po리스트에 추가

3. po리스트의 좌표에 있는 현재 사람의 인자를 찾고 pop.

저는 처음에

'벗어나면 현재 사람 리스트에서 바로 pop'

이런 식으로 구현했으나

이렇게 하면 문제가 생깁니다.

예를들어 1,2 이렇게 있는데

1에서 pop을 시킵니다.

그 다음에 2를 보는 게 아니라

그냥 리스트가 끝나버립니다.

컴퓨터 입장에서는

1하면서 pop을 했으니

더 할 게 없다고 판단.

고심끝에 저런 방식으로 처리해주니 구현이 되었습니다.

https://inspirit941.tistory.com/146

[Python] 백준 17135. 캐슬 디펜스

https://2hs-rti.tistory.com/45

[백준] 17135번 - 캐슬 디펜스 (파이썬)

다른 분들의 코드를 찾아보니

따로 사람이 움직이는 함수를 구현해주는 케이스도 있었네요.