[Python]17135. 캐슬 디펜스

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

17135번: 캐슬 디펜스

---

 

처음으로 친 상시 역량테스트의 문제.

문제를 풀기 전 제약사항이 크지 않으므로 완전탐색을 해도 되겠다고 생각했다.

 

순서도를 그려보자

 

코드는 다음과 같다.

from copy import deepcopy
 
def print_field_wall(field, wall, check, d, cnt):
    print("Distance: {}".format(d))
    for i in range(len(field)):
        print("{}\t{}".format(field[i], check[i]))
    print(wall)
    print("count: {}".format(cnt))
    print()
 
def shoot(field, wall, d, check):
    cnt = 0
    for w in range(len(wall)):
        if wall[w] == 2: # 성벽에 사수가 있다면
            for dist in range(1, d + 1): # 사격거리 1 ~ d 까지 조사 
                cont1 = True # 계속 조사 할 지 저장하는 변수
                for j in range(len(wall)): # col 순으로 시작
                    cont2 = True # 계속 조사 할 지 저장하는 변수
                    for i in range(len(field) - 1, -1, -1): # row 역순. 성벽 가까이에서 성벽 멀리 조사
                        if abs(i-len(field))+abs(j-w) == dist: # 사거리에 들어올 때
                            if field[i][j] == 1 and check[i][j] == False: # 적군이라면
                                field[i][j] = 0 # 사살하고 필드에서 없앰
                                check[i][j] = True # 사살했다는 표시
                                cnt += 1
                                cont1 = False # 3중 포문 탈출. 사수는 한번에 적군 한명만 사살가능
                                cont2 = False
                                break
                            elif field[i][j] == 0 and check[i][j] == True: # 적이 이미 사살되어서 맵에서 제거됬다면
                                cont1 = False # 3중포문 탈출
                                cont2 = False
                                break
                    if not cont2:
                        break
                if not cont1:
                    break
    return cnt
 
 
def solve(field, check, wall, d):
    global print_table
    fld = deepcopy(field) # 깊은복사(deep copy)로 mutable 방지
    chk = deepcopy(check) # 깊은복사(deep copy)로 mutable 방지
    count = 0
    if print_table:
        print("Init")
        print_field_wall(fld, wall, chk, d, count)
        
    while fld: # fld가 0 이 되면, 즉 평지에 무엇도 남아있지 않을 경우 탈출 
        count += shoot(fld, wall, d, chk) # 발사
        if print_table:
            print("Shoot")
            print_field_wall(fld, wall, chk, d, count)
        fld.pop() # 적군의 이동
        chk.pop() # 적군의 이동
        chk = [[False]*len(fld[0]) for _ in range(len(fld))] # shoot 전에 다시 초기화해줌
        if print_table:
            print("Move")
            print_field_wall(fld, wall, chk, d, count)
 
    return count
 
def main():
    global print_table
    n, m, d = map(int, input().split())
    field = [list(map(int, input().split())) for _ in range(n)]
    check = [[False]*m for _ in range(n)] # 앞의 사수에 의해 적군이 저격당했는지 확인
 
    result = 0 # 최종 정답(최댓값)
 
    # 성벽에 사수 배치. 사수가 3명이라 3중 포문
    wall = [0]*m
    for i in range(m):
        wall[i] = 2
        for j in range(i+1, m):
            wall[j] = 2
            for k in range(j+1, m):
                wall[k] = 2
 
                # 배치가 완료되면 적군 저격하는 시뮬레이션 실행(solve)
                total_count = solve(field, check, wall, d)
                if print_table:
                    print(f"***TOTAL COUNT: {total_count}***")
                    print()
 
                # 적군의 수를 비교하여 result에 할당
                result = max(total_count, result)
 
                wall[k] = 0
            wall[j] = 0
        wall[i] = 0
 
    print(result) # 결과 출력
 
if __name__ == "__main__":
    print_table = False # True 시 중간 결과물 출력, False 시 출력 안함
    main()

 

예시를 하나 살펴보자 :)

이렇게 반복하다보면..

total count 는 11이지만 이게 최댓값인지는 알 수 없다.

모든 사수 배치의 경우에서 비교를 해서 최대값을 찾아야한다.

참고로, 위 예시에서의 최대값은 14이다.