기둥과 보 설치 프로그래머스 구현문제

https://school.programmers.co.kr/learn/courses/30/lessons/60061

빙하가 깨지면서 스노우타운에 떠내려 온 “죠르디”는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. “죠르디”는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

단, 바닥은 벽면의 맨 아래 지면을 말합니다.

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.

전형적인 시뮬레이션 문제로 무작정 코드로 옮기려고 하기 보다 문제를 어떻게 하면 쉽게 해결할 수 있을지 아이디어를 머릿속으로 잘 정리한 다음에 코드를 작성하자

시간 제한은 5초로 넉넉한 편이므로 O(M^3)으로 풀어도 정답을 얻을 수 있다. 가장 간단하게 해결하는 방법은 설치 및 삭제 연산을 수행할 때 전체 구조물을 확인하여 정상인지 체크해보자

이번에도 결국 문제는 문제를 지나치게 어렵게 스스로 몰고 갔다는 점에 있습니다.

결국 우리가 리턴을(또는 출력을)할 자료를 기준으로 생각을 하면 되는데

괜히 2차원 공간의 정보를 주니(없어도됨 보면 알겠지만 불가능한 방법은 있어도 불가능한 공간에 지으려는 시도는 안함) 거기에 꽂혀서 2차원 테이블을 만들고 여기에다가 보와 기둥을 분리를 하고… 난리를 쳤는데 언제나 그렇듯 정답은 심플합니다.

결국 문제를 많이 접하고 고민을 많이 하고 보다 간단한 방법으로 생각할려고 시도를 해야 겠습니다.

#현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0:
        #설치된 것이 '기둥'인 경우
            #'바닥 위' 혹은 '보의 한쪽 끝 부분 위' 혹은 '다른 기둥 위' 라면 정상
            if y == 0 or [x-1,y,1] in answer or [x,y,1] in answer or [x,y-1,0] in answer:
                continue
            return False #아니라면 거짓 반환

stuff에서 0(기둥)인지 확인을 하고 기둥일 경우에 어떤 조건을 만족해야 설치를 할 수 있을까?

여기가 바닥 위인가 아니면 보의 한쪽인가 기둥위인가 또 다른 기둥위인가 해당 지점에 대한 정보는 어떠한지 확인을 하거나 아니면 거짓을 반환합니다.

elif stuff == 1:
        #설치된 것이 '보'인 경우
        #한쪽 끝 부분이 기둥위 혹은 양쪽 끝부분이 다른 보와 동시에 연결된다면 정상
            if ([x,y-1,0] in answer) or ([x+1, y-1, 0] in answer) or (([x-1,y,1] in answer) and ([x+1, y, 1] in answer)):
                continue
            return False #아니라면 거짓반환
    return True

보도 마찬가지 입니다. 어느 한쪽이 기둥위인가 아니면 양쪽 끝부분이 보인가. 조건문을 잘 걸어두시면 해결될 문제였습니다. 소괄호 몇개는 생략을 해도 되지만 코드의 가독성과 이해를 위해서 두었습니다.

def solution(n, build_frame):
    answer = []
    for frame in build_frame:
        x, y , stuff, operate = frame
        if operate == 0: #삭제하는 경우
            answer.remove([x,y,stuff]) #일단 삭제를 해본 뒤에
            if not possible(answer):
                answer.append([x,y,stuff])
        if operate == 1: #설치하는 경우
            answer.append([x,y,stuff])
            if not possible(answer):
                answer.remove([x,y,stuff])
    return sorted(answer)

그리고 답을 출력할 answer 리스트를 만들고 집어 넣기 시작을 합니다.

일단 조건을 떠나서 없는 것을 빼는 연산을 하지 않습니다. 그러니 무결성체크는 따로 하지 않아도 되는 걸로 보입니다. 일단 뺀다음에 이게 가능한지 체크를 하고 아니라면 다시 더하고

설치를 할때도 일단 설치를 한다음 이게 가능한지 확인을 하고 아니라면 빼버리는 식이네요

정렬하는 것도 x기준 그다음 y 등등 주어서 이것도 어떻게 정렬을 하나 따로 코드를 만들어야하나 고민을 했는데 sorted에서 다 알아서 해주는군요

전체 코드

#현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0:
        #설치된 것이 '기둥'인 경우
            #'바닥 위' 혹은 '보의 한쪽 끝 부분 위' 혹은 '다른 기둥 위' 라면 정상
            if y == 0 or [x-1,y,1] in answer or [x,y,1] in answer or [x,y-1,0] in answer:
                continue
            return False #아니라면 거짓 반환
        elif stuff == 1:
        #설치된 것이 '보'인 경우
        #한쪽 끝 부분이 기둥위 혹은 양쪽 끝부분이 다른 보와 동시에 연결된다면 정상
            if ([x,y-1,0] in answer) or ([x+1, y-1, 0] in answer) or (([x-1,y,1] in answer) and ([x+1, y, 1] in answer)):
                continue
            return False #아니라면 거짓반환
    return True

def solution(n, build_frame):
    answer = []
    for frame in build_frame:
        x, y , stuff, operate = frame
        if operate == 0: #삭제하는 경우
            answer.remove([x,y,stuff]) #일단 삭제를 해본 뒤에
            if not possible(answer):
                answer.append([x,y,stuff])
        if operate == 1: #설치하는 경우
            answer.append([x,y,stuff])
            if not possible(answer):
                answer.remove([x,y,stuff])
    return sorted(answer)