[알고리즘] 기둥과 보 설치

이영주·2021년 9월 26일
0

[문제] 기둥과 보 설치
https://programmers.co.kr/learn/courses/30/lessons/60061?language=python3

문제해결 hint

  1. 기둥 또는 보를 설치할 때 가능한 구조물인지 확인하는 함수를 작성한다.
  2. 설치 후 설치된 것이 기둥인지 보인지 확인한다.
  3. 설치된 것이 기둥인 경우 기둥 설치가 가능한 모든 조건을 확인 후 설치가 가능한 조건이면 정상이다.
  4. 문제에 따르면 기둥이 설치될 수 있는 경우는 4가지 경우이다.
    1) 맨 밑에 있는 경우
    2) 설치 아래 지점에 기둥이 있는 경우
    3) 설치 왼쪽 지점에 보가 있는 경우
    4) 설치 지점에 보가 있는 경우
  5. 설치된 것이 보인 경우 보 설치가 가능한 모든 조건을 확인 후 설치가 가능한 조건이면 정상이다.
    1) 설치 아래 지점에 기둥이 있는 경우
    2) 설치 아래 오른쪽 지점에 기둥이 있는 경우
    3) 양 옆에 보가 있는 경우
  6. 위의 조건들에 해당하지 않는 경우 기둥 또는 보가 설치될 수 없으므로 false를 반환한다.
# 현재 설치된 구조물이 가능한 구조물인지 확인하는 함수
def possible(answer):
    """
    x: 가로 좌표
    y: 세로 좌표
    stuff: 기둥 또는 보
    """
    for x, y, stuff in answer:
        # 설치된 것이 기둥인 경우
        if stuff == 0:
            # 바닥 위, 설치 지점에 보가 있는 경우, 설치 왼쪽 지점에 보가 있는 경우, 설치 아래 지점에 기둥이 있는 경우
            if (y == 0) or ([x, y, 1] in answer) or [x - 1, 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, 0] in answer) or ([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)

0개의 댓글