기둥과 보 설치*

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

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

 

해결 방법 : 단순 조건 검사

• 구조물을 설치하는 함수 construct()
  • 문제에 주어진 조건대로 기둥 or 보가 설치될 수 있는지 판별
• 구조물 삭제
  • 삭제되는 구조물이 영향을 줄 수 있는 구조물들(related)이 유지될 수 있는지 판별
    • construct 함수를 사용, (related 요소들 삭제 → 재설치(construct))검사를 통해 하나라도 재설치가 불가능하면 현재 구조물은 삭제 불가능

def solution(n, build_frame):
    answer = []
    for order in build_frame: # 구조물 order
        if order[-1] == 1: # 설치
            if construct(answer, order[:-1]):
                answer.append(order[:-1])

        else: # 삭제
            answer.remove(order[:-1]) # 현재 구조물 삭제
            canremove = True # 삭제 가능 여부
            x, y = order[0], order[1]
            related = [(x, y), (x + 1, y), (x - 1, y), (x, y + 1), (x - 1, y + 1)] # 영향을 받는 구조물들 좌표
            
            for c in answer[:]:
                if (c[0], c[1]) in related: # 영향을 받는 (존재하는) 구조물
                    answer.remove(c)
                    if not construct(answer, c): # 재설치 가능 판별
                        canremove = False
                    answer.append(c)

            if canremove == False: # 삭제 불가능
                answer.append(order[:-1]) # 현재 구조물 다시 설치
            
    return sorted(answer, key=lambda x: (x[0], x[1], x[2]))

def construct(builtList, order): # 설치 가능 판단
    x, y, k = order # x, y, kindof
    
    if k == 0: # 기둥 설치 : 해당 좌표 아래에 바닥 or 보 or 기둥이 있는지 
         return y == 0 or [x, y - 1, 0] in builtList or [x, y, 1] in builtList or [x - 1, y, 1] in builtList 

    else: # 보 설치 : 해당 좌표 아래에 기둥(오른쪽 포함) or 양쪽에 보가 있는지
        return [x, y - 1, 0] in builtList or [x + 1, y - 1, 0] in builtList or ([x - 1, y, 1] in builtList and [x + 1, y, 1] in builtList)

 

 

이전 풀이와 비교

: 똑같음