[Programmers] 기둥과 보 설치

문제 바로가기

def solution(n, build_frame):
    # 기둥들
    lines = set()
    # 보
    bo = set()

    def buildLine(x,y):
        # 바닥 위에 있거나
        if y == 0:
            return True
        # 보의 한 쪽 끝 부분 위에 있거나
        elif (x,y) in bo or (x-1, y) in bo:
            return True
        elif (x,y-1) in lines:
            return True
        return False
    def buildBo(x,y):
        # 한쪽 끝이 기둥 위에 있거나
        if (x,y-1) in lines or (x+1, y-1) in lines:
            return True
        # 양쪽 끝이 다른 보에 연결
        elif (x-1,y) in bo and (x+1,y) in bo:
            return True
        return False
    def removeLine(x,y):
        lines.remove((x,y))
        for (i,j) in [(x,y+1)]:
            if (i,j) in lines and not buildLine(i,j):
                lines.add((x,y))
                return
        for (i,j) in bo:
            if not buildBo(i,j):
                lines.add((x,y))
                return
    def removeBo(x,y): 
        bo.remove((x,y))
        for (i,j) in lines:
            if not buildLine(i,j):
                bo.add((x,y))
                return
        for (i,j) in bo:
            if not buildBo(i,j):
                bo.add((x,y))
                return
        return
    
    for (x,y,a,b) in build_frame:
        if b == 1 and a == 0:
            if buildLine(x,y):
                lines.add((x,y))
        elif b == 1 and a == 1:
            if buildBo(x,y):
                 bo.add((x,y))
        elif b == 0 and a == 0:
            removeLine(x,y)
        elif b == 0 and a == 1:
            removeBo(x,y)
    answer = []
    for (x,y) in lines:
        answer.append([x,y,0])
    for (x,y) in bo:
        answer.append([x,y,1])
    answer.sort()
    print(answer)
    return answer

lines 와 bo 에는 기둥과 보의 시작 좌표들을 넣는다. 기둥은 시작좌표가 (x,y) 라면 (x,y+1) 만큼 영향을 끼치고, bo 는 시작 좌표가 (x,y) 라면 (x+1,y) 로 오른쪽 하나만큼 이어진다.

어떻게 저장할 지가 중요하다. 처음에는 배열에 기둥이나 보가 존재하는 좌표들을 (x,y 라면 x,y와 x,y+1 에 모두) 표시하려고 했는데 단순히 존재를 표시하면 시작인지 끝인 지 확인하지 못한다는 것을 깨달았다. 그래서 set에 넣기로 결정.
buildLines과 buildBo는 각각 기둥과 보를 설치 가능한 지 확인하는 함수이다. removeLine과 removeBo 는 각각 기둥과 보를 제거하는 함수이다. 제거하는 함수의 경우에는 일단 해당 기둥과 보를 set에서 제거 한 후 기존에 존재하는 기둥이나 보가 모두 buildLines 조건들을 만족하는 지 확인하고, 만족하지 않는 기둥이나 보가 있다면 다시 제거한 기둥과 보를 추가했다.