[Python] 프로그래머스 / 2020 KAKAO BLIND RECRUITMENT / 기둥과 보 설치

문제 링크

 

"실제로 구현할 필요 없음"

 

구현, 특히 빡구현 문제들을 많이 풀고, 또한 BFS 문제를 많이 접하다보면 으레 까먹는 중요한 사실이 있다. 문제가 자신만의 상상의 나래를 펼쳐 죠르디가 기둥과 보를 짓는 이러한 문제를 풀 때, 기둥과 보를 설치하거나 철거하란다고 진짜로 설치하거나 철거할 필요는 없다는 것이다. 그런데 사실 그 유혹에 넘어가는 게 생각보다 쉽다. 왜냐하면,

 

n이 겨우 100 이하이기 때문에, 100 * 100 행렬을 만들어도 공간복잡도가 10,000 밖에 되지 않아서, 마치 이게 정답인 길 같아 보이기 때문이다. 

 

그러나 지금 이 문제에서 중요한 것은, 설치/철거 명령어 시퀀스에서 feasible한 명령만을 취한 후, 이를 sort하여 반환하는 것 뿐이다. 실제 map에 이를 구현하여 짓는 것은 전혀 중요하지 않다. 하란다고 진짜로 하는 게 매번 정답인 것은 아니다. (오늘 푼 문제들이 이런 문제가 많았어서...)

 

정답 코드

def is_possible(answer):
    for x, y, a in answer:
        if a == 0:  # 기둥
            if not (y == 0 or (x, y-1, 0) in answer or (x-1, y, 1) in answer or (x, y, 1) in answer):
                return False
        else:  # 보
            if not (((x+1, y, 1) in answer and (x-1, y, 1) in answer) or (x, y-1, 0) in answer or (x+1, y-1, 0) in answer):
                return False
    return True

def solution(n, build_frame):
    answer = set()
    
    for x, y, a, b in build_frame:
        if b == 1:  # 설치
            answer.add((x, y, a))
            if not is_possible(answer):
                answer.remove((x, y, a))
        else:  # 삭제
            answer.remove((x, y, a))
            if not is_possible(answer):
                answer.add((x, y, a))

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