title: "[프로그래머스] 기둥과 보 설치 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/60061"
description: "프로그래머스 Level 3 문제 [기둥과 보 설치]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from collections import Counter, defaultdict
N = 0

COL, ROW = 0, 1
COLHEAD, COLBOTTOM = 2, 3
ROWLEFT, ROWRIGHT = 4, 5

REMOVE, ADD = 0, 1

def is_valid(rows, cols, cnt):
    for x, y in cols:
        predicates = []
        # 바닥 위에 있거나
        predicates.append( y == 0 )
        # 보의 한쪽 끝 부분 위에 있거나
        predicates.append( cnt[(x, y)][ROW] > 0 )
        # 다른 기둥 위에 있거나
        predicates.append( cnt[(x, y)][COLHEAD] == 1 )
        
        if not any(predicates):
            return False
    
    for x, y in rows:
        predicates = []
        # 한쪽 끝 부분이 기둥 위에 있거나.
        predicates.append( cnt[(x, y)][COLHEAD] == 1 or cnt[(x+1, y)][COLHEAD] == 1 )
        # 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 함.
        predicates.append( cnt[(x, y)][ROWRIGHT] == 1 and cnt[(x+1, y)][ROWLEFT] == 1 )
        
        if not any(predicates):
            return False
    
    return True

def solution(n, build_frame):
    global N
    N = n
    
    # 각 좌표에 존재하는 기둥의 수와, 각 좌표에 걸친 보의 개수를 세는
    # 카운터를 관리합니다.
    cnt = defaultdict(Counter)
    # 기둥과 보의 좌표를 나타내는 리스트입니다.
    cols, rows = [], []
    for x, y, typ, op in build_frame:
        if typ == COL and op == ADD:
            # 기둥을 세웁니다.
            cnt[(x, y)][COLBOTTOM] += 1
            cnt[(x, y+1)][COLHEAD] += 1
            cols.append( (x, y) )
            
            if not is_valid(rows, cols, cnt):
                # 옳지 않은 구조이면, 원상복구합니다.
                cnt[(x, y)][COLBOTTOM] -= 1
                cnt[(x, y+1)][COLHEAD] -= 1
                cols.remove( (x, y) )
            
        if typ == COL and op == REMOVE:
            # 기둥을 제거합니다.
            cnt[(x, y)][COLBOTTOM] -= 1
            cnt[(x, y+1)][COLHEAD] -= 1
            cols.remove( (x, y) )
            
            if not is_valid(rows, cols, cnt):
                # 옳지 않은 구조이면, 원상복구합니다.
                cnt[(x, y)][COLBOTTOM] += 1
                cnt[(x, y+1)][COLHEAD] += 1
                cols.append( (x, y) )
            
        if typ == ROW and op == ADD:
            # 보를 설치합니다.
            cnt[(x, y)][ROW] += 1
            cnt[(x+1, y)][ROW] += 1
            cnt[(x, y)][ROWLEFT] += 1
            cnt[(x+1, y)][ROWRIGHT] += 1
            rows.append( (x, y) )
            
            if not is_valid(rows, cols, cnt):
                # 옳지 않은 구조이면, 원상복구합니다.
                cnt[(x, y)][ROW] -= 1
                cnt[(x+1, y)][ROW] -= 1
                cnt[(x, y)][ROWLEFT] -= 1
                cnt[(x+1, y)][ROWRIGHT] -= 1
                rows.remove( (x, y) )
            
        if typ == ROW and op == REMOVE:
            # 보를 제거합니다.
            cnt[(x, y)][ROW] -= 1
            cnt[(x+1, y)][ROW] -= 1
            cnt[(x, y)][ROWLEFT] -= 1
            cnt[(x+1, y)][ROWRIGHT] -= 1
            rows.remove( (x, y) )
            
            if not is_valid(rows, cols, cnt):
                # 옳지 않은 구조이면, 원상복구합니다.
                cnt[(x, y)][ROW] += 1
                cnt[(x+1, y)][ROW] += 1
                cnt[(x, y)][ROWLEFT] += 1
                cnt[(x+1, y)][ROWRIGHT] += 1
                rows.append( (x, y) )
    
    result = []
    for (x, y) in cnt.keys():
        for typ, n in cnt[(x, y)].items():
            if typ == COLBOTTOM and n > 0:
                result.append([x, y, COL])
            if typ == ROWLEFT and n > 0:
                result.append([x, y, ROW])
    
    result.sort()
    return result

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges