17135. 캐슬 디펜스

멍진이·2021년 7월 14일
0

백준 문제풀기

목록 보기
35/36

문제 링크

17135. 캐슬 디펜스

문제 코드

from itertools import combinations
from collections import deque
import copy
row,col,D = list(map(int,input().split()))

original_board = [[0 for c in range(col)]for r in range(row)]

comb_list = []

for i in range(col):
    comb_list.append(i)

archor_list = list(combinations(comb_list,3))

#print(archor_list)

for i in range(row):
    num_list = list(map(int,input().split()))
    for j in range(col):
        original_board[i][j] = num_list[j]

#print(board)

max_count = 0

for archors in archor_list:
    board = copy.deepcopy(original_board)
    kill = []
    count = 0

    for tot in range(row):
        for archor in archors:
            start = [row-1,archor]

            que = deque()

            que.append([start[0],start[1],1])
            visited = [[0 for c in range(col)]for r in range(row)]
            while len(que)>0:
                x,y,distance = que.popleft()

                if distance > D:
                    break
                if board[x][y] == 1:
                    kill.append([x,y])
                    break
                visited[x][y] = 1

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

                for i in range(3):
                    next_x = x+dx[i]
                    next_y = y+dy[i]

                    if 0<=next_x<row and 0<=next_y<col and visited[next_x][next_y] == 0:
                        que.append([next_x,next_y,distance+1])

        #print(kill)
        for die in kill:
            x,y = die
            if board[x][y] == 1:
                count+=1
                board[x][y]=0
        kill =[]
        #print(board, count)

        for i in range(row-1,0,-1):
            for j in range(col):
                board[i][j] = board[i-1][j]

        for j in range(col):
            board[0][j] = 0

        #print(board)

    max_count = max(max_count,count)


print(max_count)

문제 풀이

  • 첫번째 시도
    • 예제는 다 맞았으나 제출하자마자 틀림
    • 반례 1번에서 답이 6이 나옴
    • Kill list를 초기화하지않아서 발생하는 문제임을 파악
    • 해당 부분 해결하니 합격

반례

2 4 2
1 1 1 1
0 1 1 0
answer :5

profile
개발하는 멍멍이

0개의 댓글