파이썬으로 풀어보는 백준 17135번: 캐슬 디펜스 (삼성 A형 기출 문제)

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

17135번: 캐슬 디펜스

 

내 풀이:

N, M, D = map(int, input().split())
field_original = []
for _ in range(N):
    field_original.append(list(map(int, input().split())))
 
 
result = 0
 
 
def defense(field, hunt, index, archer1, archer2, archer3):
    global result
    if index == N:
        if result < hunt:
            result = hunt
 
        return
 
 
    D1 = D+1
    D2 = D+1
    D3 = D+1
    cnt_hunt = 0
    for i in range(N):
        for j in range(M):
            if field[i][j] == 0:
                continue
 
            if abs(i-N) + abs(j-archer1) < D1:
                D1 = abs(i-N) + abs(j-archer1)
                target1 = [i, j]
 
            if abs(i-N) + abs(j-archer2) < D2:
                D2 = abs(i-N) + abs(j-archer2)
                target2 = [i, j]
 
            if abs(i-N) + abs(j-archer3) < D3:
                D3 = abs(i-N) + abs(j-archer3)
                target3 = [i, j]
 
    if D1 < D+1:
        field[target1[0]][target1[1]] = 0
        cnt_hunt += 1
 
    if D2 < D+1:
        if field[target2[0]][target2[1]] == 1:
            field[target2[0]][target2[1]] = 0
            cnt_hunt += 1
 
    if D3 < D+1:
        if field[target3[0]][target3[1]] == 1:
            field[target3[0]][target3[1]] = 0
            cnt_hunt += 1
 
    for i in range(N-2, -1, -1):
        for j in range(M):
            field[i+1][j] = field[i][j]
 
 
    defense(field, hunt+cnt_hunt, index+1, archer1, archer2, archer3)
 
 
def archer_position(position, index):
    if index == 3:
        defense(field_original, 0, 0, position[0], position[1], position[2])
        return
 
    if index == 0:
        for _ in range(M-2):
            position.append(_)
            archer_position(position, index+1)
            del position[-1]
        return
 
    for __ in range(M):
        if max(position) >= __:
            continue
        position.append(__)
        archer_position(position, index+1)
        del position[-1]
 
archer_position([], 0)
print(result)

Python3, 오답

재귀 함수가 실행이 되지 않는다고 생각했는데 중간중간 print를 넣어가며 확인해본 결과 재귀는 실행되나 아처 3명이 배치된 후 defense()가 실행된 결과에 hunt가 계속해서 0인 것을 확인했다. 재귀 함수에 list가 들어가는 경우 이 리스트에 변화를 일으켜서 다시 재귀에 넣는 경우 shallow copy가 일어나 결과가 엉망이 돼버렸다.

 

 

N, M, D = map(int, input().split())
field_original = []
for _ in range(N):
    field_original.append(list(map(int, input().split())))
 
 
result = 0
 
 
def defense(field, hunt, index, archer1, archer2, archer3):
    global result
    if index == N:
        if result < hunt:
            result = hunt
        return
 
    D1 = D+1
    D2 = D+1
    D3 = D+1
    cnt_hunt = 0
    new_field = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            new_field[i][j] = field[i][j]
    for j in range(M):
        for i in range(N):
            if new_field[i][j] == 0:
                continue
 
            if abs(i-N) + abs(j-archer1) < D1:
                D1 = abs(i-N) + abs(j-archer1)
                target1 = [i, j]
 
            if abs(i-N) + abs(j-archer2) < D2:
                D2 = abs(i-N) + abs(j-archer2)
                target2 = [i, j]
 
            if abs(i-N) + abs(j-archer3) < D3:
                D3 = abs(i-N) + abs(j-archer3)
                target3 = [i, j]
 
 
    if D1 < D+1:
        new_field[target1[0]][target1[1]] = 0
        cnt_hunt += 1
 
    if D2 < D+1:
        if new_field[target2[0]][target2[1]] == 1:
            new_field[target2[0]][target2[1]] = 0
            cnt_hunt += 1
 
    if D3 < D+1:
        if new_field[target3[0]][target3[1]] == 1:
            new_field[target3[0]][target3[1]] = 0
            cnt_hunt += 1
 
    for i in range(N-2, -1, -1):
        for j in range(M):
            new_field[i+1][j] = new_field[i][j]
 
    for j in range(M):
        new_field[0][j] = 0
 
    defense(new_field, hunt+cnt_hunt, index+1, archer1, archer2, archer3)
 
 
def archer_position(position, idx):
    if idx == 3:
        defense(field_original, 0, 0, position[0], position[1], position[2])
        return
 
    if idx == 0:
        for _ in range(M-2):
            position.append(_)
            archer_position(position, idx+1)
            del position[-1]
        return
 
    for __ in range(M):
        if max(position) >= __:
            continue
 
        position.append(__)
        archer_position(position, idx+1)
        del position[-1]
 
archer_position([], 0)
print(result)

Python3, 764ms

shallow copy에서 발생하는 문제를 해결하고자 defense 함수 자체에서 new_field라는 리스트를 새로 만들어 사용하였다. 또한 target 탐색 순서를 세로로 우선적으로 하여 문제에서 요구하던 조건인 <같은 거리의 적의 경우 가장 왼편의 적을 공격한다>를 새로운 변수 혹은 if문 없이 해결할 수 있었다.

 

 

jinhot님의 풀이:

N, M, D = map(int, input().split())
 
board = []
 
for _ in range(N):
    board.append(list(map(int, input().split())))
 
def shoot(y, position, s_board):
    for d in range(1, D+1):
        for left in range(d, -1, -1): # left 부터 파악
            height = d - left
            if height > 0 and 0 <= y - height < N and 0 <= position - left < M and s_board[y - height][position - left] == 1:
                return (y - height, position - left)
        for right in range(1, d+1, 1): # left 부터 파악
            height = d - right
            if height > 0 and 0 <= y - height < N and 0 <= position + right < M and s_board[y - height][position + right] == 1:
                return (y - height, position + right)
        
    return None
 
def simulation(positions):
    s_board = [line[:] for line in board]
    killed_amount = 0
    for y in range(N, 0, -1):
        killed = []
        for position in positions:
            killed_enemy = shoot(y, position, s_board)
            if killed_enemy is not None:
                killed.append(killed_enemy)
        for killed_enemy in killed:
            if s_board[killed_enemy[0]][killed_enemy[1]] == 1:
                s_board[killed_enemy[0]][killed_enemy[1]] = 0
                killed_amount += 1
    return killed_amount
 
max_v = 0
for i in range(M):
    for j in range(i + 1, M):
        for k in range(j + 1, M):
            max_v = max(max_v, simulation((i, j, k)))
 
print(max_v)

Python3, 112ms

먼저 아처의 포지션을 재귀 함수가 아닌 3중 for문을 이용하여 가독성도 좋고 코딩 시간, 길이는 물론 실행 시간도 짧게 걸린다. 또한 shoot 함수가 필요로 하는 변수를 줄인 것도 눈에 띈다. simulation 함수에서 튜플로 받은 아처의 포지션 원소에 대해 함수를 실행시킨다.