2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치

오늘은 KAKAO 기둥과 보 설치를 풀어보도록 합시다.

 

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

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

코딩테스트 당시 이 문제 보자마자 그냥 바로 넘어가버렸는뎈ㅋㅋㅋㅋㅋㅋㅋ

긴장 때문에;

이번엔 맘 잡고 한 번 풀어봤습니다.

---

본 문제를 풀기 위해서 가장 중요시 했던 점은 문제에서 주어진 조건이었습니다.

 

조건 4가지를 살펴보도록 하겠습니다.

 

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야합니다.
• 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
• 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.

위의 4가지 조건이 문제를 풀기 위한 조건 4가지입니다.

 

우선 1, 2번은 check() 하나의 함수로 표현할 수 있겠습니다.

 

지금까지 지어진 건물이 건축물로서 만족하는지 알 수 있죠.

 

3번의 조건은 저희가 건물을 짓는 2차원 배열에서 참고해야하는 조건입니다.

 

우선 기둥, 보를 따로 두기 위해서 3차원 배열을 사용할 예정입니다. (arr[n][n][2])

 

arr[y][x]에 기둥을 세웠다면, arr[y + 1][x]에 또 다른 기둥을 세울 수 있겠죠?

 

4번의 조건은 주어진 build_frame을 for문으로 돌면서, 해당 행동이 만족하지 않다면 무시시키면 되는 조건입니다.

 

이렇게 4가지 조건만 만족한다면 문제를 쉽게? 해결할 수 있습니다.

 

사실 저도 어려워서 고민 많이 했던 문제였습니다. ㅠㅠ

 

저의 패착은 삭제 시 건물이 어떻게해야 조건을 만족할까 하면서 경우의 수를 세면서 문제를 푼게 패착이었는데, 지금 생각해보니 그냥 건물 자체가 조건을 만족하는지를 매번 확인하면 풀 수 있었던 문제였네요.

 

마지막 return은 for문으로 arr를 돌면서 기둥은 기둥끼리 보는 보끼리 result에 값을 넣어가면서 return 값을 구했습니다.

 

본 문제에서 가장 중요한건 check() 함수가 되겠네요

arr = [[[0, 0] for _ in range(110)] for __ in range(110)] # 기둥, 보
result = []


def check():
    for y in range(110):
        for x in range(110):
            if arr[y][x][0] == 1:
                if not (y == 0 or arr[y - 1][x][0] == 1 or arr[y][x][1] == 1 or (x - 1 >= 0 and arr[y][x - 1][1] == 1)):
                    return False
            if arr[y][x][1] == 1:
                if not (arr[y - 1][x][0] == 1 or arr[y - 1][x + 1][0] == 1 or (x - 1 >= 0 and arr[y][x - 1][1] == 1 and arr[y][x + 1][1] == 1)):
                    return False
    return True


def answer():
    for i in range(110):
        for j in range(110):
            if arr[i][j][0] == 1:
                result.append([j, i, 0])
                arr[i][j][0] = 0
            if arr[i][j][1] == 1:
                result.append([j, i, 1])
                arr[i][j][1] = 0
                
    
def build(build_frame):
    for build in build_frame:
        x, y, a, b = build
        if a == 0: # 기둥
            if b == 0: # 삭제
                arr[y][x][0] = 0
                if not check():
                    arr[y][x][0] = 1
            elif b == 1: # 설치
                arr[y][x][0] = 1
                if not check():
                    arr[y][x][0] = 0
        elif a == 1: # 보
            if b == 0: # 삭제
                arr[y][x][1] = 0
                if not check():
                    arr[y][x][1] = 1
            elif b == 1: # 설치
                arr[y][x][1] = 1
                if not check():
                    arr[y][x][1] = 0
    else:
        answer()

def solution(n, build_frame):
    build(build_frame)
    return sorted(result)

---

이상 2020 KAKAO BLIND RECRUITMENT - 기둥과 보 설치였습니다. ^_^