기둥과 보 설치

programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

def solution(n, build_frame):
    cur = []
    def canBuildOrRemove(order): # 해당 order가 가능하면 True 불가능하면 False를 반환
        x, y, a, b = order
        if b == 1: 
            if a == 0: # 기둥 설치 
                return y == 0 or [x,y,1,1] in cur or [x-1,y,1,1] in cur or [x,y-1,0,1] in cur
            else:  # 보 설치
                return y != 0 and [x,y-1,0,1] in cur or [x+1,y-1,0,1] in cur or ([x-1,y,1,1] in cur and [x+1,y,1,1] in cur)
        else:
            if order[:-1]+[1] in cur: cur.remove(order[:-1]+[1]) # 삭제할 구조물이 있으면 해당 구조물 삭제
            else: return False # 없으면 order 불가능
            
            if a== 0: # 기둥 삭제
                cases = [[x,y+1,0,1], [x,y+1,1,1], [x-1,y+1,1,1]]
            else: # 보 삭제
                cases = [[x,y,0,1], [x+1,y,0,1], [x-1,y,1,1], [x+1,y,1,1]]
                
            t = [True for i in range(len(cases))]
            for i in range(len(cases)):
                if cases[i] in cur: # 현재 order가 영향을 주는 구조물들이 존재하면 유지 가능한지 판단
                    cur.remove(cases[i])
                    t[i] = canBuildOrRemove(cases[i])
                    cur.append(cases[i])
                    
            cur.append(order[:-1]+[1]) # 삭제한 구조물을 일단 다시 설치
            return sum(t) == len(t) # order가 영향을 주는 모든 구조물이 유지 가능하면 True 
    
    for build in build_frame:
        if canBuildOrRemove(build) == True: # 해당 order가 실행 가능하면,
            if build[3] == 1: cur.append(build) # 설치 order이면 설치
            else: cur.remove(build[:-1]+[1]) # 삭제 order이면 삭제
    
    return sorted([c[:-1] for c in cur], key=lambda x: (x[0],x[1],x[2]))

→ 구조물을 설치하는 조건은 간단하다.

하지만 구조물을 없앨때 고려해야 하는 부분이 많기 때문에 모든 경우를 조건문으로 걸기 힘들다.

따라서 삭제할 구조물이 유지에 영향을 줄 수 있는 또 다른 구조물들을 대상으로 

이 구조물들을 없애고 다시 설치하는것이 가능한지를 판단하는식으로 구현하였음.