BOJ 17135번 캐슬 디펜스 풀던 이야기

삼성 코테 스타일과 비슷하다는 이야기를 듣고 17135번을 풀기 시작했습니다. 주어지는 문제의 탐색 범위가 크지 않으므로 선형 탐색을 사용하고 그 범위만 줄이기로 했습니다. 단순 구현이었으므로 그리 오래 안 걸릴 것이라고 생각했는데...

가벼웠던 시작

공격 사거리를 기반으로 궁수 위에 직사각형 영역을 만들어 해당 영역을 선형 탐색하며 공격 대상을 찾은 뒤 한 번에 제거, 턴이 끝나면 궁수를 한 줄 위로 올리는 방식을 사용했습니다.

from sys import stdin, stdout
import itertools

def getDistanceOfTwo(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)

def copyBoard(arr):
    newBoard = []
    for row in arr:
        newBoard.append(row.copy())
    return newBoard

# def printBoard(arr):
#     for row in arr:
#         for cell in row:
#             print(cell, end=' ')
#         print()
#     print()

class Archer:
    def __init__(self, x):
        self.x = x
        self.attacks = (100, 100)

boardRows, boardCols, archerRange = map(int, stdin.readline().split(' '))

assert 3 <= boardCols and boardCols <= 15
assert 3 <= boardRows and boardRows <= 15
assert 1 <= archerRange <= 10

board = [[0] * boardCols] * boardRows
for row in range(boardRows):
    board[row] = list(map(int, stdin.readline().split(' ')))
    assert len(board[row]) == boardCols

EMPTY = 0
ENEMY_EXISTS = 1
X = 0
Y = 1

howManyArchers = 3
archerXCoordRange = range(boardCols)
archerXCoordCombinations = itertools.combinations(archerXCoordRange, howManyArchers)
maxNumAttackedEnemies = -1
for archerXCoordCombination in archerXCoordCombinations:
    currentBoard = copyBoard(board)
    currentBoardRows = boardRows
    
    archers = [Archer(archerXCoordCombination[0]), Archer(archerXCoordCombination[1]), Archer(archerXCoordCombination[2])]
    currentAttackedEnemies = 0
    while currentBoardRows > 0:
        archerYCoord = currentBoardRows
        for archer in archers:
            searchYUpperBound = archerYCoord - archerRange if archerYCoord - archerRange > 0 else 0
            searchYLowerBound = archerYCoord - 1
            assert searchYUpperBound <= searchYLowerBound
            searchXLeftBound = archer.x - archerRange + 1 if archer.x - archerRange + 1 > 0 else 0
            searchXRightBound = archer.x + archerRange - 1 if archer.x + archerRange - 1 < boardCols else boardCols - 1
            assert searchXLeftBound <= searchXRightBound

            for y in range(searchYUpperBound, searchYLowerBound + 1):
                for x in range(searchXLeftBound, searchXRightBound + 1):
                    currentCell = currentBoard[y][x]
                    if currentCell == EMPTY:
                        continue
                    assert currentCell == ENEMY_EXISTS
                    distanceFromArcher = getDistanceOfTwo(archer.x, archerYCoord, x, y)
                    if distanceFromArcher > archerRange:
                        continue
                    assert distanceFromArcher <= archerRange
                    existingEnemyDistanceFromArcher = getDistanceOfTwo(archer.attacks[X], archer.attacks[Y], archer.x, archerYCoord)
                    if distanceFromArcher <= existingEnemyDistanceFromArcher:
                        if distanceFromArcher < existingEnemyDistanceFromArcher:
                            archer.attacks = (x, y)
                        elif distanceFromArcher == existingEnemyDistanceFromArcher:
                            if x < archer.attacks[X]:
                                archer.attacks = (x, y)
            assert archerYCoord == currentBoardRows
            
        for archer in archers:
            if archer.attacks == (100, 100):
                continue
            attackedCell = currentBoard[archer.attacks[Y]][archer.attacks[X]]
            if attackedCell == ENEMY_EXISTS:
                currentBoard[archer.attacks[Y]][archer.attacks[X]] = EMPTY
                currentAttackedEnemies += 1
            	archer.attacks = (100, 100)
                #printBoard(currentBoard)
                #print(currentAttackedEnemies, end='\n\n')

        currentBoardRows -= 1

    if currentAttackedEnemies > maxNumAttackedEnemies:
        maxNumAttackedEnemies = currentAttackedEnemies
        maxAttackPosition = archerXCoordCombination

stdout.write(str(maxNumAttackedEnemies) + '\n')

가볍지 않았던 현실

단 하나, 6번째 테스트 케이스를 통과하지 못했습니다.

6번 테스트케이스를 돌리면 정답인 14보다 1 작은 13을 자꾸 답으로 뱉었습니다. printBoard 함수로 단계별 보드 상황을 확인해 본 결과 적 하나를 자꾸 놓치고 있었는데... 웃기게도 질문 게시판의 온갖 반례들은 모두 간단히 통과했습니다.
한 줄 한 줄 디버깅하기엔 과정이 너무 길어지므로 가장 먼저, 코드에서 놓친 부분이 없는지 살펴 보았습니다. 서로 다른 궁수가 같은 대상을 공격할 때의 경우를 제대로 처리하는가? 최소 거리의 서로 다른 공격 대상이 둘 이상 있을 때 왼쪽 대상을 먼저 공격하는가? 탐색 범위 설정은 적절한가? 등등, 온갖 경우의 수를 생각해 보며 코드를 검토했습니다. 이 과정에서, 처음에 짰던 코드보다 탐색을 덜 해도 된다는 사실을 알고 탐색 범위를 다음과 같이 수정했습니다.

searchYUpperBound = archerYCoord - archerRange if archerYCoord - archerRange > 0 else 0
searchYLowerBound = archerYCoord - 1
assert searchYUpperBound <= searchYLowerBound
searchXLeftBound = archer.x - archerRange + 1 if archer.x - archerRange + 1 > 0 else 0
searchXRightBound = archer.x + archerRange - 1 if archer.x + archerRange - 1 < boardCols else boardCols - 1
assert searchXLeftBound <= searchXRightBound

궁수가 밑변 중점에서 한 칸 아래에 있도록 하는, 너비가 (archerRange - 1) * 2 + 1이고 높이가 archerRange인 직사각형 영역을 탐색하도록 한 내용입니다.

그런데 이건 효율 개선일 뿐, 6번 테스트 케이스를 통과하지 못하는 이유는 여전히 불명이었습니다. 경험적으로, 이런 문제는 엄청 사소한 실수에 의한 것이란 사실을 알고 있었으므로, 실수를 잡기 위해 assert를 좀 더 활용해 보기로 했습니다.

범인 잡아라

이미 여러 부분에 assert를 사용해 어느 정도 필터링을 해 둔 상태였으므로 제가 "에이 이건 assert 없이도 당연히 충족하지 않을까?" 하면서 넘겼던 조건을 찾아 보기로 했습니다. 코드 전체를 몇 번씩 검토해 보고 나서, 선형 탐색하는 부분의 이중 for문 끝에서 진짜로 궁수의 위쪽 적만을 노리고 있는지 검사해 보기로 했습니다. 처음 수정한 코드는 다음과 같습니다. 설마설마 하며 다음 코드의 마지막 한 줄을 추가했다.

for y in range(searchYUpperBound, searchYLowerBound + 1):
    for x in range(searchXLeftBound, searchXRightBound + 1):
        assert archer.attacks[Y] == 100 or archer.attacks[Y] < archerYCoord
        currentCell = currentBoard[y][x]
        if currentCell == EMPTY:
            continue
        assert currentCell == ENEMY_EXISTS
        distanceFromArcher = getDistanceOfTwo(archer.x, archerYCoord, x, y)
        if distanceFromArcher > archerRange:
            continue
        assert distanceFromArcher <= archerRange
        existingEnemyDistanceFromArcher = getDistanceOfTwo(archer.attacks[X], archer.attacks[Y], archer.x, archerYCoord)
        if distanceFromArcher <= existingEnemyDistanceFromArcher:
            if distanceFromArcher < existingEnemyDistanceFromArcher:
                archer.attacks = (x, y)
            elif distanceFromArcher == existingEnemyDistanceFromArcher:
                if x < archer.attacks[X]:
                    archer.attacks = (x, y)
assert archer.attacks[Y] == 100 or archer.attacks[Y] < archerYCoord

가볍게 돌려 봤으나, 바로 assert에 걸렸습니다. ??

이중 for문 내부에 코드를 넣어 보고 나서도 돌려 봤으나 결과는 같았습니다. 궁수가 존재하는 줄에 잔존한 적을 공격하는 상황이 생긴 겁니다. 그것도 6번 테스트 케이스에서만. 결국 다시 코드를 훑어 보며 무엇이 문제인가 생각해 봤습니다. 곰곰이 생각해 보니, 번뜩 이런 생각이 들었습니다.

"이전 턴에서 찾은 공격 대상 중 하나가 (100, 100)으로 초기화되지 않고 남아있던 게 아닐까?"

그래서 차례가 끝나기 전에 공격 대상을 (100, 100)으로 초기화하는 부분을 다시 검토해 보았습니다.

for archer in archers:
    if archer.attacks == (100, 100):
        continue
    attackedCell = currentBoard[archer.attacks[Y]][archer.attacks[X]]
    if attackedCell == ENEMY_EXISTS:
        currentBoard[archer.attacks[Y]][archer.attacks[X]] = EMPTY
        currentAttackedEnemies += 1
        archer.attacks = (100, 100)

처음 딱 보았을 때는 별 이상한 느낌은 없었는데, 적이 존재하여 공격에 성공했을 때만 마지막 줄이 실행된다는 사실을 깨달았습니다. 즉 왼쪽 궁수가 먼저 적을 처치했다면 값이 초기화되지 않았던 것... 그래서 공격 성공 여부에 관계없이 해당 코드가 실행될 수 있도록 다음과 같이 코드를 수정했습니다.

for archer in archers:
    if archer.attacks == (100, 100):
        continue
    attackedCell = currentBoard[archer.attacks[Y]][archer.attacks[X]]
    if attackedCell == ENEMY_EXISTS:
        currentBoard[archer.attacks[Y]][archer.attacks[X]] = EMPTY
        currentAttackedEnemies += 1
    archer.attacks = (100, 100)

테스트 케이스를 모두 통과했고 제출하여 통과까지 상황 종료.

결론

실수를 안 할 수는 없지만 내 실수를 기계가 찾도록 하는 최고의 방법이라는 생각을 하게 되었습니다. 어렵다 PS...