[프로그래머스] Lv3 기둥과 보 설치

🔗 문제 링크

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

프로그래머스

 

📝  풀이

문제를 처음 읽고 구현문제라는 것을 알 수 있어야한다. 또한 n제한이 100이고 build_frame의 최대 길이가 1000이므로 시간복잡도를 고려안해도 되는 구현문제라는 것을 알 수있다. 하지만 문제가 매우 헷갈리기도 했고 조건을 구현하기 매우 어려웠다. 특히, 특정 좌표에서 보와 기둥을 둘 다 지을 수 있다는 것을 체크해야한다.

일단 build_frame에 따라 기둥이나 보를 짓거나 없애고 전체 조건을 검사하는 방식으로 진행했다. 또한 값이 0인 경우는 기둥, 1은 보, 2는 둘 다 지어졌다고 가정했다. 

 

1. 단순 범위 체크를 위한 메서드를 구현한다.

def isValid(x,y,n):
    if 0 <= x < n and 0 <= y < n:
        return True
    return False

 

2. 기둥을 지을 수 있는지 없는지 판별하는 메서드를 구현한다.

def canBuildPillow(i,j,build):
    if j == len(build)-1: # 좌표의 맨 위라면 벽면을 넘어가므로 지을 수 없다.
        return False
    # 기둥의 조건
    # 바닥 위에 있거나 
    if j == 0:
        return True
    # 보의 한쪽 끝 부분 위에 있거나 (왼쪽 보)
    if isValid(i-1,j,len(build)):
        if build[i-1][j] == 1 or build[i-1][j] == 2:
            return True
    # 보의 한쪽 끝 부분 위에 있거나 (오른쪽 보)
    if isValid(i,j,len(build)):
        if build[i][j] == 1 or build[i][j] == 2:
            return True
    #  또 다른 기둥 위에 있어야 한다.
    if isValid(i,j-1,len(build)):
        if build[i][j-1] == 0 or build[i][j-1] == 2:
            return True

    return False # 통과 못함

3. 보를 지을 수 있는지 없는지 판별하는 메서드를 구현한다.

def canBuildBeam(i,j,build):
    # 맨 오른쪽인 경우 벽면을 넘어가므로 지을 수 없다.
    if i == len(build)-1:
        return False
    # 한쪽 끝 부분이 기둥 위에 있거나 
    if isValid(i,j-1,len(build)):
        if build[i][j-1] == 0 or build[i][j-1] == 2:
            return True
    if isValid(i+1,j-1,len(build)):
        if build[i+1][j-1] == 0 or build[i+1][j-1] == 2:
            return True
    # 양쪽 끝 부분이 다른 보와 동시에 연결되어있어야 한다.
    if isValid(i-1,j,len(build)) and (build[i-1][j] == 1 or build[i-1][j] == 2) and isValid(i+1,j,len(build)) and (build[i+1][j] == 1 or build[i+1][j] == 2):
        return True
    return False

4.  전체 build를 순회하면서 모든 보와 기둥들이 지을 수 있는지 없는지 판별하는 메서드를 구한다.

def isPossible(build):
    # 모든 건축물들을 순회한다.
    for i in range(len(build)):
        for j in range(len(build)):
            if build[i][j] == -1: # 아무것도 안지어진 경우
                continue
            else: # 보나 기둥이 있는 경우
                if build[i][j] == 0: # 기둥인 경우
                    if not canBuildPillow(i,j,build):
                        return False
                        
                if build[i][j] == 1: # 보인 경우
                    if not canBuildBeam(i,j,build):
                        return False
                        
                if build[i][j] == 2: # 둘다 설치
                    if not canBuildPillow(i,j,build):
                        return False
                    if not canBuildBeam(i,j,build):
                        return False
    return True

5. 위에서 구현한 메서드들을 활용해서 문제를 푼다.

def solution(n, build_frame):
    # 아무것도 안지은 상태로 -1로 초기화한다.
    build = [[-1 for i in range(n+1)] for i in range(n+1)]
    
    for i in range(len(build_frame)):
        x,y,a,b = build_frame[i][0],build_frame[i][1],build_frame[i][2],build_frame[i][3]
        
        # 지을 수 없는 경우 복구하기 위해 이전값 저장
        tmp = build[x][y]
        
        if b == 0: # 삭제
            if build[x][y] == 2:
                if a == 0:
                    build[x][y] = 1
                if a == 1:
                    build[x][y] = 0
            else:
                build[x][y] = -1
                
        if b == 1: # 생성
            if build[x][y] == -1:
                build[x][y] = a
            else:
                build[x][y] = 2
            
        if not isPossible(build):
            build[x][y] = tmp
            #print(str(x)+str(y),str(a)+"설치안함")
    answer = []
    
    for i in range(len(build)):
        for j in range(len(build)):
            if build[i][j] == 0 or build[i][j] == 1:
                answer.append([i,j,build[i][j]])
            if build[i][j] == 2:
                answer.append([i,j,0])
                answer.append([i,j,1])
    
    return answer

🖥 최종 코드

 

def isValid(x,y,n):
    if 0 <= x < n and 0 <= y < n:
        return True
    return False
def canBuildPillow(i,j,build):
    if j == len(build)-1:
        return False
    # 기둥의 조건
    # 바닥 위에 있거나 
    if j == 0:
        return True
    # 보의 한쪽 끝 부분 위에 있거나 또 다른 기둥 위에 있어야 한다.
    if isValid(i-1,j,len(build)):
        if build[i-1][j] == 1 or build[i-1][j] == 2:
            return True
    #  또 다른 기둥 위에 있어야 한다.
    if isValid(i,j-1,len(build)):
        if build[i][j-1] == 0 or build[i][j-1] == 2:
            return True
    # ----
    if isValid(i,j,len(build)):
        if build[i][j] == 1 or build[i][j] == 2:
            return True
    return False # 통과 못함
def canBuildBeam(i,j,build):
    # 맨 오른쪽인 경우
    if i == len(build)-1:
        return False
    # 한쪽 끝 부분이 기둥 위에 있거나 
    if isValid(i,j-1,len(build)):
        if build[i][j-1] == 0 or build[i][j-1] == 2:
            return True
    if isValid(i+1,j-1,len(build)):
        if build[i+1][j-1] == 0 or build[i+1][j-1] == 2:
            return True
    # 양쪽 끝 부분이 다른 보와 동시에 연결되어있어야 한다.
    if isValid(i-1,j,len(build)) and (build[i-1][j] == 1 or build[i-1][j] == 2) and isValid(i+1,j,len(build)) and (build[i+1][j] == 1 or build[i+1][j] == 2):
        return True
    return False

def isPossible(build):
    for i in range(len(build)):
        for j in range(len(build)):
            if build[i][j] == -1:
                continue
            else: # 보나 기둥이 있는 경우
                if build[i][j] == 0: # 기둥인 경우
                    if not canBuildPillow(i,j,build):
                        return False
                        
                if build[i][j] == 1: # 보인 경우
                    if not canBuildBeam(i,j,build):
                        return False
                if build[i][j] == 2: # 둘다 설치
                    if not canBuildPillow(i,j,build):
                        return False
                    if not canBuildBeam(i,j,build):
                        return False
    return True

def solution(n, build_frame):
    
    build = [[-1 for i in range(n+1)] for i in range(n+1)]
    
    for i in range(len(build_frame)):
        x,y,a,b = build_frame[i][0],build_frame[i][1],build_frame[i][2],build_frame[i][3]
        
        # 이전값 저장
        tmp = build[x][y]
        
        if b == 0: # 삭제
            if build[x][y] == 2:
                if a == 0:
                    build[x][y] = 1
                if a == 1:
                    build[x][y] = 0
            else:
                build[x][y] = -1
                
        if b == 1: # 생성
            if build[x][y] == -1:
                build[x][y] = a
            else:
                build[x][y] = 2
            
        if not isPossible(build):
            build[x][y] = tmp
            #print(str(x)+str(y),str(a)+"설치안함")
    answer = []
    
    for i in range(len(build)):
        for j in range(len(build)):
            if build[i][j] == 0 or build[i][j] == 1:
                answer.append([i,j,build[i][j]])
            if build[i][j] == 2:
                answer.append([i,j,0])
                answer.append([i,j,1])
    
    return answer