기둥과 보 설치

문제

---

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

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

 

 

나의 풀이

---

처음엔 2차원 배열을 사용해 문제를 풀려고 했지만 생각해보면 각 상황을 2차원 배열로 나타내기에 어렵다는 걸 알 수 있다. 배열은 각 칸을 기준으로 값을 저장하는데 문제에선 위치 좌표에 따라 선에 기둥이나 보를 설치하기 때문이다. 따라서, set을 사용해 각 조건을 만족하는지 검사하였다. building은 설치된 기둥과 보의 정보를 (x,y,a)의 형태로 담고 있는 set이다.

먼저 기둥(x,y,0,1)을 설치하기 위한 조건은 다음과 같다.

1. 바닥 위에 설치하는 경우 if y == 0
2. 보의 한 쪽 끝의 위에 설치하는 경우 if (x-1,y,1) in building or (x,y,1) in building
3. 다른 기둥의 위에 설치하는 경우 if (x,y-1,0) in building

보(x,y,1,1)을 설치하기 위한 조건은 다음과 같다.

1. 보의 한 쪽 끝이 기둥의 위에 연결된 경우 if (x,y-1,0) in building or (x+1,y-1,0) in building
2. 보의 양 끝이 다른 보와 각각 연결된 경우 if (x-1,y,1) in building and (x+1,y,1) in building

삭제하는 경우엔 해당 기둥이나 보를 삭제한 뒤 남은 기둥과 보들이 위의 조건을 모두 만족하는지 검사하면 된다.

set을 사용해 탐색에 시간을 줄일 수 있고, 설치하는 경우엔 check 함수를 통해 검사하는 시간이 O(1)이다. 또한 삭제하는 경우 모든 기둥과 보에 대해 반복문을 사용해 유효한지 검사를 하지만 삭제하는 경우에만 해당되고 각 경우에 대한 check 함수를 구동하는 시간 또한 O(1)이므로 최대 O(n)이 걸린다. 여기서 n은 해당 시점에 building에 있는 원소의 수이다. 

 

코드

---

import copy

building = set()

def check(x, y, a, s):
    # (x,y) 시작점으로 하는 기둥이 조건을 만족하는지 검사
    if a == 0:
        # (x,y)가 바닥 위에 있는 경우
        if y == 0:
            return True
        # (x,y)가 보의 한 쪽 끝 위에 있는 경우
        elif (x-1,y,1) in s or (x,y,1) in s:
            return True
        # (x,y)가 다른 기둥 위에 있는 경우
        elif (x,y-1,0) in s:
            return True
    # (x,y)를 시작점으로 하는 보가 조건을 만족하는지 검사
    elif a == 1:
        # 보의 한 쪽 끝이 기둥 위에 있는 경우
        if (x,y-1,0) in s or (x+1,y-1,0) in s:
            return True
        # 보의 양 끝이 다른 보와 연결된 경우
        elif (x-1,y,1) in s and (x+1,y,1) in s:
            return True
    return False

def solution(n, build_frame):
    answer = [[]]
    for x,y,a,b in build_frame:
        # 설치하는 경우
        if b == 1:
            if check(x,y,a,building):
                building.add((x,y,a))
        # 삭제하는 경우
        elif b == 0:
            tmp = copy.deepcopy(building)
            tmp.remove((x,y,a))
            flag = 0
            for z,w,c in tmp:
                if not check(z,w,c,tmp):
                    flag = 1
                    break
            # 삭제가 불가능한 경우
            if flag == 1:
                continue
            else:
                building.remove((x,y,a))
    answer = list(building)
    answer.sort(key = lambda x : (x[0],x[1],x[2]))

    return answer