[완전탐색,파이썬] 기둥과 보 설치 4/18 - 4/19

# 기둥과 보 설치

## 목적: 기둥과 보를 이용하여 벽을 세우는 로봇

## 행의 순서가 거꾸로 돼있어서 좌표를 어떻게 표시해야하는지 곤란했지만 x,y를 y,x로 바꾸자 해결이 됐다.

## 처음 아이디어는 board에 보의 경우 2, 기둥의 경우 1을 처리하고 나머지는 0으로 하여 문제를 해결하고자 했는데 보와 기둥이 겹치는 부분을 1로 해야할지 2로 해야할지 곤란했으며 둘 중ㅇ 하나를 삭제하면 0으로 바꿔야하는지 1로 바꿔야 하는지도 난감했다.

## 그래서 결국 답을 확인해보기로 결정했다.

## 생각의 오류1. x,y에서 구조물이 설치되므로 nx,ny는 고려할 필요가 없다. 보가 양쪽에서 동시에 설치되는 경우 제외

-> x,y 그리고 x-1,y로 확인해볼 수 있음!
## 나는 board의 숫자를 바꿔서 확인을 하려고 했다. 그런데, 위에서 같은 문제가 발생했잖아.
## 해답지는 이 result에 추가를 해서 확인을 했다. 그니깐 x,y,stuff넣고 만약 다른 기둥 위가 정상이라고 하면 그 정보를 넣어주는거지. x, y-1, stuff가 다른 기둥 위를 나타내니깐 이걸로 검사를 한다.

-> 좌표를 실제로 생각하지 않고 그냥 x,y만 넣어서 확인을 했다. 이렇게 좌표를 실제로 생각하며 만들지 않아도 된다. 왜일까?

 

 

# 기둥과 보 설치

## 목적: 기둥과 보를 이용하여 벽을 세우는 로봇

## 이차원 맵 리스트 n x n
## 기둥과 보 표현 0,1
## 이동표현 dx, dy
## 보는 오른쪽, 기둥은 위쪽
# 기둥의 경우 위쪽이므로 0,1 nx와 x를 연결하기
# 보의 경우 오른쪽이므로 1,0
# 기둥은 
# 조건1) 바닥 위에 있거나 행이 -> 0행에 대해서만 해당 
# 조건2)보의 한쪽 끝 -> 해당하는 보가 있는 지 확인하기 
# 조건3)다른 기둥 위 -> 해당하는 기둥이 있는 지 확인하기
# 보는
# 조건1) 한쪽 끝이 기둥 -> 해당하는 기둥이 있는 지 확인하기
# 조건2) 양쪽이 다른 보 -> 양쪽 보 확인
# 어려운 점: 좌표를 어떻게 표현하지?
# build_Frame을 전체 하나씩 확인한다.
# 먼저 그 좌표를 보고 있는지 없는지 확인한다.
# 설치인가 삭제인가? 삭제라면, 있으면 삭제하기
# 설치라면,
# 기둥인가 보인가?
# 기둥이라면 기둥 조건을 만족하는가? 보라면 보의 조건을 만족하는가?
# 설치하고 정보에 추가하기 tuple
# 설치한 정보를 result에 추가하기.

def solution(n, build_frame):
    #기둥, 보 1,2
    step = [(0,1), (1,0)]
    gidung = []
    bo = []
    answer = [[]]
    
    board = [ [0] * (n+1) for _ in range(n+1) ]
    
    for frame in build_frame:
        x = frame[1]
        y = frame[0]
        a = frame[2]
        b = frame[3]
        
        #설치
        if b == 1:
            #보
            if a == 1:
                nx, ny = x + 1 , y
                #양쪽이 보인 경우
                if board[x][y] == 2 and board[nx][ny] == 2:
                    answer.append([y,x,a])
                #양쪽이 기둥인 경우
                elif board[x][y] == 1 and board[nx][ny] == 1:
                    answer.append([y,x,a])
                #한쪽만 기둥인 경우
                elif board[x][y] == 1:
                    board[nx][ny] = 2
                    answer.append([y,x,a])
                #한쪽만 기둥인 경우
                elif board[nx][ny] == 1:
                    board[x][y] = 2
                    answer.append([y,x,a])
            #기둥
            elif a == 0:
                nx, ny = x, y + 1      
        #삭제
        elif b == 0:
            #보인경우
            if a == 1:
                for i in answer:
                    if i[0] == y and i[1] == x:
                        board
                        answer.remove(i)
                
            #기둥인경우
            elif a == 0:
            
    return answer

처음 작성한 코드에서 큰 뼈대 부분은 맞았지만 각각의 경우를 설치하는 것을 어떻게 코드로 나타낼 수 있는지가 어려웠다.

 

해답지의 경우에는 이를 possible로 구분하였다.

 

일단 설치해두고 전체 구조물들이 조건을 만족하는지 모두 n**2번 확인하는 것이다. 만약 조건을 만족하지 않으면 다시 삭제해주면 된다.

그리고 삭제하는 경우에도 일단 삭제해보고 전체 구조물들이 조건을 만족하는지 모두 n**2번 확인하는 것이다. 만약 조건을 만족하지 않으면 다시 설치해주면 된다.

 

여기서 핵심은 세세하게 구현할 수 없으니, 일단 설치나 삭제를 해보고 나서 전체 구조물이 조건을 만족하는 지 확인해주고, 다시 복구해준다는 것에 있다!

 

def possible (answer):
	#모든 구조물이 조건을 만족하는지 확인하기 인덱싱 주의!
    for result in answer:
        x,y,a = result
        if a == 0: #pillar
            if not (y == 0 or [x-1,y,1] in answer or [x+1,y,1] in answer or [x,y-1,0] in answer):
                return False
        elif a == 1: #bo
            if not ([x,y-1,0] in answer or [x+1,y-1,0] in answer or ([x-1,y,1] in answer and [x + 1, y, 1] in answer)):
                return False
    return True

def solution(n, build_frame):
    answer = []
    
    for build in build_frame:
        x,y,a,b = build
        
        if b == 1: #install
        	#일단 설치해보고 안되면 삭제하기
            answer.append([x,y,a])
            if not possible(answer):
                answer.remove([x,y,a])
        elif b == 0: #remove
        	#일단 삭제해보고 안되면 설치하기
            answer.remove([x,y,a])
            if not possible(answer):
                    answer.append([x,y,a])
                    
    answer = sorted(answer)
    return answer

기둥의 조건에서 x+1이 아니고 x임!