[Programmers] 기둥과 보 설치

문제

n x n 격자 벽면에 기둥과 보를 설치하거나 삭제하면서, 매 작업 후 남아 있는 모든 구조물이 조건을 만족해야 하는 문제. 기둥은 바닥 위에 있거나, 아래에 기둥이 있거나, 보의 한쪽 끝 위에 있어야 한다. 보는 한쪽 끝이 기둥 위에 있거나, 양쪽 끝이 다른 보와 연결되어 있어야 한다. 

 

명령은 [x, y, a, b] 형태로 주어지고, a는 기둥/보, b는 설치/삭제를 의미한다. 최종적으로 남은 구조물을 x 오름차순, y 오름차순, 기둥 먼저 정렬해서 반환해야 한다. 조건 자체가 복잡해서, 설치와 삭제 각각의 경우를 미리 전부 따지려 하면 코드가 쉽게 꼬이는 구현 문제다.

회고

처음에는 명령을 그대로 따라가면서 모든 경우의 수를 직접 나누려고 했는데 (먼저 b가 1이면 설치, 0이면 삭제로 나누고, 그 안에서 다시 a가 1이면 보, 0이면 기둥으로 나누는 식...) 그러다 보니 조건이 괴랄할 정도로 많아진데다, 특히 삭제 쪽 구현은 주변 구조물이 같이 무너지는 상황을 고려해야 해서 고민하다 포기 선언을 했다.

 

제한 조건 상, build_frame의 길이가 최대 1000이고, 구조물 개수도 그 정도를 크게 벗어나지 않는데다, 그렇다면 매 명령마다 전체 구조물을 한 번씩 검사해도 충분히 감당 가능한 크기라는 점이 문제의 핵심. 따라서 명령을 일단 적용하고, 현재 남아 있는 모든 구조물이 유효한지만 검사해도 충분히 풀 수 있는 조건이고, 하나라도 조건을 어기면 방금 한 작업을 되돌리는 식으로 풀었다. 핵심은 적용 -> 전체 검사 -> 실패하면 원복이다. 백트래킹에서 상태를 바꿨다가 되돌리는 방식과 거의 비슷하다.

 

또 하나 중요한 부분은 자료구조였다. 정답 코드에는 리스트에 구조물을 넣고 [x, y, a] in answer 형태로 존재 여부를 확인했는데, AI가 추천해주기를 리스트에서 in은 선형 탐색이기 때문에 (명령 수가 최대 1000이라 통과는 가능하지만) set로 하는 편이 훨씬 자연스럽다고. 대신 리스트는 set에 넣을 수 없으므로 구조물을 (x, y, a) 튜플로 관리해야 한다는 점은 기억할 것. 

 

def solution(n, build_frame):
    structures = set()

    def is_valid_one(x, y, a):
        if a == 0:
            return (
                y == 0
                or (x, y - 1, 0) in structures
                or (x - 1, y, 1) in structures
                or (x, y, 1) in structures
            )

        return (
            (x, y - 1, 0) in structures
            or (x + 1, y - 1, 0) in structures
            or ((x - 1, y, 1) in structures and (x + 1, y, 1) in structures)
        )

    def is_valid():
        return all(is_valid_one(x, y, a) for x, y, a in structures)

    for x, y, a, b in build_frame:
        item = (x, y, a)

        if b == 1:
            structures.add(item)
            if not is_valid():
                structures.remove(item)
        else:
            structures.remove(item)
            if not is_valid():
                structures.add(item)

    return sorted([list(item) for item in structures])