[알고리즘] 프로그래머스 - 기둥과 보 설치

프로그래머스 - 기둥과 보 설치

실패한 내 풀이

from collections import defaultdict


"""
1. 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
2. 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
"""

def column_constructable(x, y, constructed_frames, n):
    if y == 0: # 바닥 위에 있는 경우
        return True

    if (x-1, y) in constructed_frames and 1 in constructed_frames[(x-1,y)]: #보의 한쪽 끝 부분에 있거나
        return True

    if (x, y-1) in constructed_frames and 0 in constructed_frames[(x,y-1)]: # 다른 기둥 위에 있는 경우.
        return True

    return False


def row_constructable(x, y, constructed_frames, n):
    if ((x, y-1) in constructed_frames and 0 in constructed_frames[(x,y-1)]) or ((x+1, y-1) in constructed_frames and 0 in constructed_frames[(x+1, y-1)]): # 보는 한쪽 끝 부분이 기둥 위에 있거나
        return True
    
    if ((x-1, y) in constructed_frames and 1 in constructed_frames[(x-1,y)]) and ((x+1, y) in constructed_frames and 1 in constructed_frames[(x+1,y)]): #또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
        return True

    return False


def column_destructable(x, y, constructed_frames, n):
    destructable = True
    constructed_frames[(x,y)].remove(0)

    if (x, y-1) in constructed_frames and 0 in constructed_frames[(x,y-1)]:
        destructable = destructable and column_constructable(x, y-1, constructed_frames, n)

    if (x -1, y) in constructed_frames and 1 in constructed_frames[(x - 1, y)]:
        destructable = destructable and row_constructable(x - 1, y, constructed_frames, n)

    if (x + 1, y) in constructed_frames and 1 in constructed_frames[(x + 1,y)]:
        destructable = destructable and row_constructable(x + 1, y, constructed_frames, n)

    constructed_frames[(x,y)].append(0)
    return destructable


def row_destructable(x, y, constructed_frames, n):
    destructable = True
    constructed_frames[(x,y)].remove(1)

    if (x, y) in constructed_frames and 0 in constructed_frames[(x,y)]:
        destructable = destructable and column_constructable(x, y, constructed_frames, n)

    if (x+1, y) in constructed_frames and 0 in constructed_frames[(x + 1,y)]:
        destructable = destructable and column_constructable(x + 1, y, constructed_frames, n)

    if (x-1, y) in constructed_frames and 1 in constructed_frames[(x - 1,y)]:
        destructable = destructable and row_constructable(x - 1, y, constructed_frames, n)

    if 1 in constructed_frames[(x + 1,y)]:
        destructable = destructable and row_constructable(x + 1, y, constructed_frames, n)

    constructed_frames[(x,y)].append(1)
    return destructable


def solution(n, build_frame):
    constructed_frames = defaultdict(list)
    constructed_frames_list = list()

    for frame in build_frame:
        x, y, construct_type, cmd = frame
        if cmd == 1: # 설치
            if construct_type == 0 : # 기둥
                if column_constructable(x, y, constructed_frames, n):
                    constructed_frames[(x,y)].append(0)
                    constructed_frames_list.append([x, y, 0])
            else: # 보
                if row_constructable(x, y, constructed_frames, n):
                    constructed_frames[(x,y)].append(1)
                    constructed_frames_list.append([x, y, 1])

        else: # 철거
            if construct_type == 0 : # 기둥
                if column_destructable(x, y, constructed_frames, n):
                    constructed_frames[(x,y)].remove(0)
                    constructed_frames_list.remove([x, y, 0])
            else: # 보
                if row_destructable(x, y, constructed_frames, n):
                    constructed_frames[(x,y)].remove(1)
                    constructed_frames_list.remove([x, y, 0])

    print(constructed_frames)
    print(sorted(constructed_frames_list))
    return sorted(constructed_frames_list)

테스트케이스는 통과했는데 실제 케이스에서 거의 런타임 에러가 났다.

다른 사람 풀이

def isValid(answer):
    for x,y,a in answer:
        if a==0:
            if (x,y-1,0) in answer or (x-1,y,1) in answer or (x,y,1) in answer or y==0:
                continue
            else:
                return False
        if a==1:
            if (x,y-1,0) in answer or (x+1,y-1,0) in answer or ((x-1,y,1) in answer and (x+1,y,1) in answer):
                continue
            else:
                return False
    return True

def solution(n, build_frame):
    answer = set()
    for x,y,a,b in build_frame:
        if b==0:
            answer.remove((x,y,a))
            if not isValid(answer):
                answer.add((x,y,a))
        else:
            answer.add((x,y,a))
            if not isValid(answer):
                answer.remove((x,y,a))

    answer = [list(i) for i in answer]
    answer.sort(key=lambda x:(x[0],x[1],x[2]))
    return answer