카카오 기출 - 기둥과 보 설치

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

접근

기둥배열과 보 배열을 각 각 따로 이차원 배열로 생성해주었고. 기둥과 보의 시작점과 끝점을 각각 1로 설정해준후 구현하였음.

1차 수정

0ㅡ0ㅡ0 보가 이렇게 지어져있을 때나,
0ㅡxㅡ0 이렇게 지어져있을 때나 이차원 배열의 값은 같기 떄문에 구별이 안된다. 그리하여 시작점만 1로 설정해주는 식으로 변경하였다

처음 코드

def solution(n, build_frame):
    # 기둥은 바닥위에 있거나 보의 한 쪽 끝 부분 위에 있거나 다른 기둥위
    # 보는 한쪽 끝이 기둥 위 or 양쪽 끝부분이 다른 보
    gi=[[0 for i in range(n+1)] for j in range(n+1)]
    bo=[[0 for i in range(n+1)] for j in range(n+1)]
    
    for bu in build_frame:
        x,y,a,b=bu
        # x y는 교차점 좌표고 교차점 기준으로 보는 오른쪽 기둥은 위쪽
        if a==0:
            # 기둥
            if b==0:
                flag=True
                # first 위에 기둥
                if gi[y+1][x]==1:
                    if not (bo[y+1][x]==1 or bo[y+1][x-1]==1):
                        flag=False
                
                # second 오른쪽에 보
                if bo[y+1][x]==1:
                    if not(gi[y][x+1]==1 or (bo[y+1][x-1]==1 and bo[y+1][x+1]==1)):
                        flag=False
                        
                # third 왼쪽에 보
                if bo[y+1][x-1]==1:
                    if not(gi[y][x]==1 or (bo[y+1][x-2]==1 and bo[y+1][x]==1)):
                        flag=False

                if flag:
                    gi[y][x]=0

            else:
                # 설치
                if y==0 or gi[y-1][x]==1 or bo[y][x]==1 or bo[y][x-1]==1:
                    # 바닥이거나 기둥위거나 보 위에
                    gi[y][x]=1
        else:
            if b==0:
                flag=True
                # 삭제
                # first 왼쪽에 기둥
                if gi[y][x]==1:
                    if not(bo[y][x]==1 or bo[y][x-1]==1 or y==0):
                        flag=False
                        
                # second 오른쪽에 기둥
                if gi[y][x+1]==1:
                    if not(bo[y][x+1]==1 or bo[y][x]==1 or y==0):
                        flag=False

                # third 오른쪽에 보
                if bo[y][x+1]==1:
                    if not(gi[y-1][x+1]==1 or gi[y-1][x+2]==1):
                        flag=False
                
                # fourth 왼쪽에 보
                if bo[y][x-1]==1:
                    if not(gi[y-1][x-1]==1 or gi[y-1][x]==1):
                        flag=False
                if flag:
                    bo[y][x]=0
            else:
                if (bo[y][x+1]==1 and bo[y][x-1]==1) or gi[y-1][x+1]==1 or gi[y-1][x]==1:
                    # 다른 기둥의 한 쪽 위거나 양쪽이 보
                    bo[y][x]=1
            
            
        
    answer = []
    
    for i in  range(n+1):
        for j in range(n+1):
            if gi[i][j]==1:
                answer.append([j,i,0])
            if bo[i][j]==1:
                answer.append([j,i,1])
    answer.sort()
    return answer

예제는 모두 통과하였으나 실 테스트 케이스는 반타작

2차 수정

초기코드에는 기둥 혹은 보를 삭제해줄때 해당 보 혹은 기둥많이 영향을 끼치는 부분만 고려하여 코드를 구현하였으나, 이부분에서 문제가 있었다.

인접 보와 기둥은 유지가 가능하더라도, 연쇄적으로 확장해봤을때 조건에 부합하지 않는 보와 기둥이 생길 수 도 있기때문에, 삭제 연산이 들어올 때마다 전체 기둥과 보의 적합성을 판단해야함

수정된 코드

def delete(i,j,gb,gi,bo,n):
    if gb==0:
        # 기둥
        gi[i][j]=0
    else:
        # 보
        bo[i][j]=0
    count=0
    for y in range(n+1):
        for x in range(n+1):
            if gi[y][x]==1:
                if not(y==0 or gi[y-1][x]==1 or bo[y][x]==1 or bo[y][x-1]==1):
                    return False
            if bo[y][x]==1:
                if not((bo[y][x+1]==1 and bo[y][x-1]==1) or gi[y-1][x+1]==1 or gi[y-1][x]==1):
                    return False


    return True
    


def solution(n, build_frame):
    # 기둥은 바닥위에 있거나 보의 한 쪽 끝 부분 위에 있거나 다른 기둥위
    # 보는 한쪽 끝이 기둥 위 or 양쪽 끝부분이 다른 보
    gi=[[0 for i in range(n+1)] for j in range(n+1)]
    bo=[[0 for i in range(n+1)] for j in range(n+1)]
    
    for bu in build_frame:
        x,y,a,b=bu
        # x y는 교차점 좌표고 교차점 기준으로 보는 오른쪽 기둥은 위쪽
        if a==0:
            # 기둥
            if b==0:
                # 기둥 삭제
                if not delete(y,x,a,gi,bo,n):
                    gi[y][x]=1
                    
            else:
                # 설치
                if y==0 or gi[y-1][x]==1 or bo[y][x]==1 or bo[y][x-1]==1:
                    # 바닥이거나 기둥위거나 보 위에
                    gi[y][x]=1
        else:
            if b==0:
                if not delete(y,x,a,gi,bo,n):
                    bo[y][x]=1
            else:
                if (bo[y][x+1]==1 and bo[y][x-1]==1) or gi[y-1][x+1]==1 or gi[y-1][x]==1:
                    # 다른 기둥의 한 쪽 위거나 양쪽이 보
                    bo[y][x]=1
            
            
        
    answer = []
    
    for i in  range(n+1):
        for j in range(n+1):
            if gi[i][j]==1:
                answer.append([j,i,0])
            if bo[i][j]==1:
                answer.append([j,i,1])
    answer.sort()
    return answer

참고

사고 확장하기
데이터 그래프로 표현할때는 정확하게 되었는지 확인