[프로그래머스] 기둥과 보 설치 - Python

이번에 해결해 볼 문제는 프로그래머스에 있는 기둥과 보 설치이다.

---

문제 설명

1. 2차원 가상 벽면에 길이가 1인 기둥과 보를 세우려고 한다.
2. 기둥과 보를 세우기 위한 규칙은 다음과 같다.
   • 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제한다.
   • 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없다.
   • 바닥에 보를 설치하는 경우는 없다.
   • 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않는다.
   • 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분에 있거나, 또는 다른 기둥 위에 있어야 한다.
   • 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.
   • 만약 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시된다.
3. 설치된 구조물을 다음과 같은 규칙으로 출력하면 됩니다.
   • x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬
   • x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오도록 정렬

문제 해결 아이디어

• 해당 문제를 처음 접하였을 때 2차원 가상 벽면을 구현을 어떻게 할지 고민했다. 하지만 주어지는 입력이 1,000개가 최대이고 설치 또는 삭제 좌표가 직접 주어지므로 굳이 2차원 가상 벽면을 2차원 배열로 구현할 필요가 없음을 깨달았다.
  • 좌표를 하나의 배열에 담아 규칙을 만족하는지 모든 구조물에 대해 검사하는 것이 충분히 가능하다.

문제 해결 코드

def check(arr):
    """
    문제 설명 2번에서 bold체로 되어 있는 부분을 구현
    """
    for fx, fy, fa in arr:
        if fa == 0:
            if fy == 0: continue # 기둥이 바닥에 있는 경우
            elif [fx, fy-1, 0] in arr: continue # 현재 기둥 아래 기둥이 있는 경우
            elif [fx-1, fy, 1] in arr or [fx, fy, 1] in arr: continue # 보의 한쪽 끝에 있는 경우
            return False
        else:
            if [fx, fy-1, 0] in arr or [fx+1, fy-1, 0] in arr: continue # 보 한쪽 끝에 기둥이 있는 경우
            elif [fx-1, fy, 1] in arr and [fx+1, fy, 1] in arr: continue # 양쪽 끝 부분이 다른 보와 연결된 경우
            return False
    return True

def solution(n, build_frame):
    frame = []
    for x, y, a, b in build_frame:
        if b == 1: # 설치하는 경우
            frame.append([x, y, a]) # 우선 설치
            if not check(frame): frame.pop() # 규칙을 위반한다면 다시 삭제
        else: # 삭제하는 경우
            frame.remove([x, y, a]) # 우선 삭제
            if not check(frame): frame.append([x, y, a]) # 규칙을 위반한다면 다시 설치

    frame = sorted(frame, key=lambda x:(x[0],x[1],x[2]))

    return frame