기둥과 보 설치

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