[프로그래머스] 기둥과 보

문제

• 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치한다. 기둥과 보는 길이가 1인 선분으로 표시되고 다음과 같은 규칙을 갖는다.
  • 기동 : 바닥 위에 있거나, 보의 한 쪽 끝 부분 위에 있거나, 다른 기둥 위에 있어야 한다.
  • 보 : 한쪽 끝 부분이 기둥 위에 있거나, 다른 보와 동시에 연결되어 있어야 한다.
• 기둥과 보를 설치, 제거 하는 명령어들이 주어질 때 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시된다.
• 모든 명령을 수행한 후 구조물의 상태를 리턴하기
  • x 좌표 -> y 좌표 -> 구조물 종류(기둥 -> 보) 순으로 오름차순 정렬
• 5 <= 벽면의 크기 <= 100
  1 <= 명령어 개수 <= 1000

 

풀이 

• 구현 문제이고, 명령어 개수가 1000개로 적다.

 

• 기둥 (위로 설치)
  • 바닥 위 : y 좌표가 0
  • 보의 한쪽 끝 부분 위 : (x, y, 1) 또는 (x-1, y, 1) 가 이미 있어야 함
  • 다른 기둥 위 : (x, y-1, 0) 이 있어야 함
• 보 (오른쪽으로 설치)
  • 한 쪽 끝 부분이 기둥 위 : (x, y-1, 0) 또는 (x+1, y-1, 0) 이 있어야 함
  • 양쪽 끝 부분이 다른 보와 동시에 연결 : (x, y, 1) and (x+1, y, 1)  이 있어야 함
• 삭제 : 해당 구조물 제거하고 다른 구조물들을 온전히 설치할 수 있는지 확인하기

 

def is_possible(table, x, y, a) :
    # 기둥 설치
    if a == 0 :
        # 1) 바닥이거나 2) 보의 한 쪽 끝 부분 위에 있거나 3) 다른 기둥 위에 있어야 한다.
        if y == 0 or (x, y, 1) in table or (x-1, y, 1) in table or (x, y-1, 0) in table:
            return True
    elif a == 1 :
        # 1) 한쪽 끝 부분이 기둥 위에 있거나 2) 다른 보와 동시에 연결
        if (x, y-1, 0) in table or (x+1, y-1, 0) in table or ((x-1, y, 1) in table and (x+1, y, 1) in table) :
            return True
    return False

def solution(n, build_frame):
    table = set()   # (x 좌표, y 좌표, 구조물 종류)
    
    for x, y, a, b in build_frame :
        # 설치
        if b == 1 and is_possible(table, x, y, a) :
                table.add((x, y, a))
        # 삭제
        elif b == 0 :
            # 해당 구조물을 삭한 뒤, 다른 구조물들이 모두 잘 설치될 수 있는지 확인하기
            table.remove((x, y, a))     
            for nx, ny, na in table :
                if (nx, ny, na) in table and not is_possible(table, nx, ny, na) :
                    table.add((x, y, a))
                    break

    
    return sorted(list(table))

 

References

• 프로그래머스 Lv3 기둥과 보