[Python] 프로그래머스 level3 기둥과 보 설치

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

 

풀이 과정 

• 보와 기둥의 설치 조건을 빠트리지만 않으면 되는 문제다.
• 삭제할 때는 삭제를 하고, 조건에 안 맞는 기둥이나 보가 있는지 확인하고, 있다면 다시 삭제하기 전으로 되돌리는 게 편하다.
• 보의 존재 유무를 이차원 배열 bo에 저장한다. bo [x][y]=True라면 (x,y)에 보가 존재하는 것
• 기둥의 존재 유무를 이차원 배열 piller에 저장한다. piller[x][y]=True라면 (x,y)에 기둥이 존재하는 것 
• 기둥 설치 조건 : 바닥 위에 있거나, 보의 한쪽 끝 부분 위에 있거나, 또다른 기둥 위에 있거나 -> bo[x][y] or (x > 0 and bo[x - 1][y]) or y == 0 or piller[x][y - 1]
• 보 설치 조건 : 한쪽 끝 부분이 기둥 위에 있거나, 양쪽 끝 부분이 다른 보와 동시에 연결되어 있거나 -> (y>0 and piller[x][y-1]) or (y>0 and x<n and piller[x+1][y-1]) or (bo[x-1][y] and bo[x+1][y])

 

전체 코드

# 기둥과 보 설치
def bo_check(x, y, bo, piller):
    n = len(bo)
    if (y>0 and piller[x][y-1]) or (y>0 and x<n and piller[x+1][y-1]) or (bo[x-1][y] and bo[x+1][y]):
        return True
    return False

def piller_check(x, y, bo, piller):
    if bo[x][y] or (x > 0 and bo[x - 1][y]) or y == 0 or piller[x][y - 1]:
        return True
    return False
def delete_check(bo, piller):
    n = len(bo)
    for x in range(n):
        for y in range(n):
            if bo[x][y] and not bo_check(x, y, bo, piller):
                return False
            if piller[x][y] and not piller_check(x, y, bo, piller):
                return False
    return True

def solution(n, build_frame):
    piller = [[0]*(n+1) for _ in range(n+1)]
    bo = [[0]*(n+1) for _ in range(n+1)]
    for x, y, a, b in build_frame:
        if b == 1: # 추가
            if a == 1: # 보
                if bo_check(x, y, bo, piller):
                    bo[x][y] = 1
            elif a == 0:
                if piller_check(x, y, bo, piller):
                    piller[x][y] = 1
        else:
            if a == 1:
                bo[x][y] = 0
                if not delete_check(bo, piller):
                    bo[x][y] = 1
            elif a == 0:
                piller[x][y] = 0
                if not delete_check(bo, piller):
                    piller[x][y] = 1

    answer = []
    for i in range(n+1):
        for j in range(n+1):
            if piller[i][j]:
                answer.append([i, j, 0])
            if bo[i][j]:
                answer.append([i, j, 1])
    return answer