[Programmers] 기둥과 보 설치 (Lv.3) 2024/4/1

문제 제목	정답률	난이도
기둥과 보 설치	35%	Lv.3

 

프로그래머스

 

문제요약

구조물(기둥, 보) 설치 삭제에 대한 배열 build_frame이 주어진다.

조건 1) 모든 기둥은 땅에 설치되거나, 보의 한쪽 끝 위에 있거나, 또 다른 기둥 위에 있다.

조건 2) 모든 보는 땅 위에 있지 않고, 한쪽 끝이 기둥 위에 있거나, 양쪽 끝이 보와 연결되어 있어야 한다.

각 삽입, 삭제마다 조건1) 조건2)를 만족시켜야 한다(만족시키지 않는 행위에 대해서는 무시하고 다음 행위를 진행)

answer=모든 구조물 결과 : [[x, y, 0|1],...]]로 구성되어 있고 오름차순 정렬이어야 한다.

 

풀이

Step1. 특정 기둥이나 보가 조건1, 조건2를 만족하는지 확인

• 특정 기둥이 조건을 만족하는지 확인
• 특정 보가 조건을 만족하는지 확인

Step2. 삽입, 삭제에 대해 연산 수행이 가능한지 확인

• 삽입의 경우 해당 x, y에 대해 step1을 진행
• 삭제의 경우 삭제한 뒤에 영향을 받는 모든 기둥, 보에 대해 step1을 진행

 

※※ 책의 풀이는 possible함수를 이용해 삽입 삭제 시 모든 answer에 대해 가능한지 탐색하는데

해당 풀이의 경우 삽입, 삭제가 일어날때마다 특정 기둥, 특정 보에 대해 is_build_okay인지 판단하게 하였다.

(삽입의 경우 1개, 삭제의 경우 6가지의 기둥이나 보에 대해 탐색)

코드의 길이는 증가하지만, 조금 더 엄밀하게 연산을 진행하도록 하였다.

def is_build_okay(x, y, type, answer):
    if type==0: #기둥-> 바닥위, 보의 한쪽 끝 부분 위, 다른 기둥 위
        if y==0 or [x-1, y, 1] in answer or [x, y, 1] in answer or [x, y-1, 0] in answer:
            return True
    else:
        if y>0:
            if [x, y-1, 0] in answer or [x+1, y-1, 0] in answer:
                return True
            if [x-1, y, 1] in answer and [x+1, y, 1] in answer:
                return True
    return False

def solution(n, build_frame):

    answer=[]
    for now in build_frame:
        if now[3]==0: #삭제
            all_okay=True
            check_answer_xy=[]
            check_answer_xy=[xy for xy in [[now[0]-1, now[1], 1], [now[0], now[1], 1], [now[0]-1, now[1]+1, 1], [now[0], now[1]+1, 1], [now[0]+1, now[1], 1]] if xy in answer]
            check_answer_xy+=[xy for xy in [[now[0], now[1]-1, 0], [now[0], now[1], 0],  [now[0], now[1]+1, 0], [now[0]+1, now[1]-1, 0],[now[0]+1, now[1], 0]] if xy in answer]
            
            temp_answer=answer[:]
            
            if now[2]==0:
                temp_answer.remove([now[0], now[1], 0])
            else:
                temp_answer.remove([now[0], now[1], 1])
                
            for xy in check_answer_xy:
                all_okay=is_build_okay(xy[0], xy[1], xy[2], temp_answer)
                if all_okay==False:
                    break
                    
            if all_okay==True:
                if now[2]==0:
                    answer.remove([now[0], now[1], 0])
                else:
                    answer.remove([now[0], now[1], 1])
        else:
            if now[2]==0: #기둥
                if is_build_okay(now[0], now[1], 0, answer):#설치
                    answer.append([now[0], now[1], 0])
            else: #보 조건
                if is_build_okay(now[0], now[1], 1, answer):#설치
                    answer.append([now[0], now[1], 1])
    answer.sort()
    return answer