문제 링크

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

문제 설명

• 기둥과 보를 설치하는 순서가 주어짐
• 설치가 가능할 경우 설치
• 삭제가 가능할 경우 삭제
• 최종 결과물 리턴

풀이

• 실제로 board 에 설치, 삭제
• 설치
  • 하나라도 있으면 가능
  • 보
    • 아래에 기둥이 있을 경우
    • 오른쪽 아래에 기둥이 있을 경우
    • 양 쪽에 보가 있을 경우
  • 기둥
    • 바닥일 경우
    • 왼쪽에 보가 있을 경우
    • 그 자리에 보가 있을 경우
    • 아래에 기둥이 있을 경우
• 삭제
  • 실제로 삭제
  • 해당 구조물이 필요한 구조물이 그 자리에 위치(설치) 가능한지 재귀적으로 검사
  • 다시 설치

코드

def solution(n, build_frame):
    board = [[[0, 0] for _ in range(n+1)] for _ in range(n+1)]
    for x, y, blanket, install in build_frame:
        if possible(board, y, x, blanket, install):
            board[y][x][blanket] = install
    answer = []
    for x in range(n+1):
        for y in range(n+1):
            if board[y][x][0]:
                answer.append([x, y, 0])
            if board[y][x][1]:
                answer.append([x, y, 1])
    return answer


def possible(board, y, x, blanket, install):
    if install:
        if blanket:
            # 아래 기둥
            if y-1 >= 0:
                if board[y-1][x][0]:
                    return True
            # 오른쪽 아래 기둥
            if y-1 >= 0 and x+1 < len(board):
                if board[y-1][x+1][0]:
                    return True
            # 양쪽 보
            if x-1 >= 0 and x+1 < len(board):
                if board[y][x-1][1] and board[y][x+1][1]:
                    return True
        else:
            # 바닥
            if y == 0:
                return True
            # 왼쪽 보
            if x-1 >= 0:
                if board[y][x-1][1]:
                    return True
            # 그자리 보
            if board[y][x][1]:
                return True
            # 아래 기둥
            if y-1 >= 0:
                if board[y-1][x][0]:
                    return True
    else:
        result = True
        board[y][x][blanket] = 0
        if blanket:
            # 왼쪽 보 설치
            if x-1 >= 0:
                if board[y][x-1][1]:
                    if not possible(board, y, x-1, 1, 1):
                        result = False
            # 오른쪽 보 설치
            if x+1 < len(board):
                if board[y][x+1][1]:
                    if not possible(board, y, x+1, 1, 1):
                        result = False
            # 그자리 기둥 설치
            if board[y][x][0]:
                if not possible(board, y, x, 0, 1):
                    result = False
            # 오른쪽 기둥 설치
            if x+1 < len(board):
                if board[y][x+1][0]:
                    if not possible(board, y, x+1, 0, 1):
                        result = False
        else:
            # 왼쪽 위 보 설치
            if y+1 <= len(board) and x-1 >= 0:
                if board[y+1][x-1][1]:
                    if not possible(board, y+1, x-1, 1, 1):
                        result = False
            # 위 보 설치
            if y+1 < len(board):
                if board[y+1][x][1]:
                    if not possible(board, y+1, x, 1, 1):
                        result = False
            # 위 기둥 설치
            if y+1 < len(board):
                if board[y+1][x][0]:
                    if not possible(board, y+1, x, 0, 1):
                        result = False
        board[y][x][blanket] = 1
        return result