이해

• n x n 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치한다. 각 격자는 1 x 1 크기이고, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있다.
  • 기둥: 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.
  • 보: 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.
• 벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 주어진다.
  • build_frame: 원소는 [x, y, a, b]형태이며 (x, y)는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이다. a 값이 0이면 기둥을 나타내고 1이면 보를 나타낸다. b 값이 0이면 삭제를 나타내고 1이면 설치를 나타낸다.
• 최종 구조물의 상태는 배열로 표현되며 배열의 원소는 각 구조물의 좌표를 담고있어야 한다.
  • 배열의 원소는 [x, y, a]형식이며 (x, y)는 기둥, 보의 교차점 좌표이고 a는 구조물의 종류를 나타낸다. a가 0이면 기둥을 나타내고 1이면 보를 나타낸다.
  • x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순으로 정렬하고, x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오도록 정렬한다.
• 최종 구조물의 상태를 return하라.

계획

• 빈 구조물부터 시작해서 입력받은 build_frames 배열의 원소를 하나씩 반영해보며 임시로 만들어진 구조물이 가능한 구조물인지를 체크해준다.
• 가능한 구조물인지 확인해주는 함수를 하나 정의한다.
  • 구조물에 설치된 모든 기둥과 보를 탐색한다.
    • 기둥인 경우에는 기둥이 바닥 위에 있거나 보의 한쪽 끝부분 위에 있거나 다른 기둥 위에 있는지를 확인해준다.
    • 보인 경우에는 한쪽 끝 부분이 기둥 위에 있거나 양쪽 끝 부분이 다른 보와 연결되어 있는지를 확인해준다.
    • 위의 조건을 만족하지 않는 기둥이나 보가 하나라도 있으면 False를 반환한다.
• build_frames 배열의 모든 원소를 반영해본 후에 만들어지는 최종 구조물을 return한다.

실행

import copy

def is_possible(structure):
    for elem in structure:
        x, y, a = elem
        # 기둥
        if a == 0:
            # not (바닥 위 or 다른 기둥 위 or 바로 왼쪽에 보 or 바로 오른쪽에 보)
            if not (y == 0 or [x, y-1, 0] in structure or [x-1, y, 1] in structure or [x, y, 1] in structure):
                return False
        # 보
        else:
            # not (왼쪽 끝 부분이 기둥 위 or 오른쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시에 연결)
            if not ([x, y-1, 0] in structure or [x+1, y-1, 0] in structure or ([x-1, y, 1] in structure and [x+1, y, 1] in structure)):
                return False
    return True

def solution(n, build_frame):
    result = []
    
    for elem in build_frame:
        x, y, a, b = elem
        # 삭제
        temp = copy.deepcopy(result)
        if b == 0:
            temp.remove([x, y, a])
            if is_possible(temp):
                result.remove([x, y, a])
        # 추가
        else:
            temp.append([x, y, a])
            if is_possible(temp):
                result.append([x, y, a])
    result.sort()
    return result

개선

• deepcopy를 하지 않고도 구현이 가능하다.

import copy

def is_possible(structure):
    for elem in structure:
        x, y, a = elem
        # 기둥
        if a == 0:
            # not (바닥 위 or 다른 기둥 위 or 바로 왼쪽에 보 or 바로 오른쪽에 보)
            if not (y == 0 or [x, y-1, 0] in structure or [x-1, y, 1] in structure or [x, y, 1] in structure):
                return False
        # 보
        else:
            # not (왼쪽 끝 부분이 기둥 위 or 오른쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시에 연결)
            if not ([x, y-1, 0] in structure or [x+1, y-1, 0] in structure or ([x-1, y, 1] in structure and [x+1, y, 1] in structure)):
                return False
    return True

def solution(n, build_frame):
    result = []
    
    for elem in build_frame:
        x, y, a, b = elem
        # 삭제
        if b == 0:
            result.remove([x, y, a])
            if not is_possible(result):
                result.append([x, y, a])
        # 추가
        else:
            result.append([x, y, a])
            if not is_possible(result):
                result.remove([x, y, a])
    result.sort()
    return result

회고

• 예전에 이 문제를 푼 적이 있어서 그때의 기억으로 막힘없이 잘 풀었다.
• 자잘한 실수 없이 모든 테스트 케이스를 한 번에 통과하였다. 난이도가 있는 문제였는데 한 번에 통과해서 기뻤다. 예전에는 쉬운 문제를 풀 때에도 자잘한 실수를 자주 하곤 했는데 체계적으로 계획을 완벽히 세운 후에 코드를 작성하니까 확실히 실수를 덜 하는 것 같다.