[프로그래머스] 기둥과 보 설치 (구현, 카카오)

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

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

graph = None
 
 
def is_possible(x, y):
    if graph[x][y] == 1:  # 기둥
        # 바닥이거나 // 보의 오른쪽 끝 부분 위에 있거나(왼쪽 끝에 있으면 같은 위치이므로 3) // 다른 기둥 위거나
        if y == 0 or (x > 0 and graph[x - 1][y] >= 2) or graph[x][y - 1] in (1, 3):
            return True
        else:
            return False
    elif graph[x][y] == 2:  # 보
        # 한쪽 끝 부분이 기둥 위에 있거나 // 양쪽 끝 부분이 다른 보와 동시에 연결
        if graph[x][y - 1] in (1, 3) or graph[x + 1][y - 1] in (1, 3) \
                or (x > 0 and graph[x - 1][y] >= 2 and graph[x + 1][y] >= 2):
            return True
        else:
            return False
    else:  # 기둥과 보 함께 설치
        # 다른 기둥 위거나 // 양쪽 끝 부분이 다른 보와 동시에 연결되거나 // 오른쪽 기둥 위거나
        if graph[x][y - 1] in (1, 3) or (x > 0 and graph[x - 1][y] >= 2 and graph[x + 1][y] >= 2) \
                or graph[x + 1][y - 1] in (1, 3):
            return True
        else:
            return False
 
 
def solution(n, build_frame):
    global graph
    graph = [[0] * (n + 1) for _ in range(n + 1)]
 
    for frame in build_frame:
        x, y, a, b = frame
        now = graph[x][y]
        a += 1
 
        if b == 0:
            graph[x][y] -= a
        else:
            graph[x][y] += a
 
        for i in range(n + 1):
            flag = False
            for j in range(n + 1):
                if graph[i][j] != 0 and not is_possible(i, j):
                    flag = True
                    graph[x][y] = now
                    break
            if flag:
                break
 
    answer = list()
    for i in range(n + 1):
        for j in range(n + 1):
            if graph[i][j] == 1:
                answer.append([i, j, 0])
            elif graph[i][j] == 2:
                answer.append([i, j, 1])
            elif graph[i][j] == 3:
                answer.append([i, j, 0])
                answer.append([i, j, 1])
    return answer

카카오 구현 문제는 정말 까다로운 것 같다..

이번 문제도 구현문제라서 문제에서 설명해주는대로 풀면 되지만, 꽤나 고생했다.

 

내가 구현한 코드에서 중요한 부분은, 첫째로 문제에서와 다르게 기둥을 1, 보를 2로 둔 것이다.

격자에 구조물을 표시해야 하는데, 기둥을 0으로 하면 더해도 표시가 안나기 때문이다. 기둥과 보가 같은 좌표에 있으면 더해서 3을 표시한다.

 

둘째로, 구조물 리스트(다른 언어에서는 벡터나 배열로 주어질 것)에서 새로운 구조물을 가져오면서 계속 이를 적용하고, 모든 구조물에 대해 조건을 만족하는지 확인한 것이다. 지우거나 추가하는 부분에 연결된 부분만 검사하면, 연쇄적으로 문제가 생기는 부분을 잡지 못할 수 있다. n이 최대 100, 구조물의 갯수가 최대 1000개이니 최대치로 검사해도 100000번이다. 그냥 완전탐색을 유도한 것 같다.

 

셋째로, 문제의 매개변수 조건을 잘 읽어서, 쓸데없는 조건을 넣지 않은 것이다. 문제를 잘 보면, 보는 바닥에 깔리지 않고, 벽면을 벗어나는 구조물은 없다. 그런 조건까지 없었으면 코드가 진짜 우주로 갔을 것 같다.

 

카카오 공채 문제는 진짜 보면 볼수록 잘 만든 것 같다는 생각을 하게 된다.