기둥과 보
2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치한다. 기둥과 보는 길이가 1인 선분이며, 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다. 또한 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 보와 동시에 연결되어 있어야 한다.
(바닥은 벽면의 맨 아래 지면을 말한다.)
2차원 벽면은 NXN 크기의 정사각 격자 형태이며, 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있다.
만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시된다.
입력 : 벽면의 크기 n, 기둥과 보를 설치/삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame
출력 : 구조물의 상태 ( [x,y,a] 의 리스트)
제한 사항
- build_frame의 원소는 [x,y,a,b]
- x,y 는 기둥,보를 설치 또는 삭제할 교차점의 좌표 [가로,세로]
- a는 0 기둥, 1 보
- b는 0 삭제, 1 설치
- 벽면을 벗어나게 기둥,보를 설치하지 않는다.
- 바닥에 보를 설치하는 경우는 없다.
- 기둥은 위, 보는 오른쪽 방향으로 설치/삭제 한다.
- 구조물이 겹치도록 설치하는 경우와 없는 구조물을 삭제하는 경우는 없다.
- return
- [x,y,a]
- x,y 좌표, a 0 기둥, 1 보
- x 좌표 기준으로 오름차순 정렬, y 오름차순 정렬, x,y 같을 경우 기둥이 보보다 앞에
접근
자자 Gabojago ~ !
이것도 완전 탐색! 모든 경우를 하나씩 체크하면서 진행할 예정
하나씩 answer 리스트에 추가 또는 삭제한 후 answer list의 각 교차점들이 해당 조건을 만족하는지 판단하는 함수를 통해 검사를 진행하여 만족하는 경우 리스트에 추가 아닌 경우 삭제 하는 식의 논리로 접근한다.
거의 다 했는데,, 비슷하게 했는데,, 참지 못하고 힌트 봐버렸당,,
그래서 그냥 쓴당
먼저 각 answer list의 요소들이 해당 조건을 만족하는지 판단하는 함수를 작성한다. 기둥인 경우 바닥 위, 보의 한쪽 끝 부분, 다른 기둥 위를 검사, 보인 경우 한쪽 끝 부분이 기둥 위, 또는 양 쪽 끝 부분이 보와 연결을 검사!
def check(answer):
for x,y,a in answer:
if a == 0: #기둥인 경우
if y==0 or [x,y-1,0] in answer or [x-1,y,1] in answer or [x,y,1] in answer:
continue
return False
elif a == 1: #보인 경우
if [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):
continue
return False
return True삭제인 경우와 설치 인 경우를 반복문을 돌며 검사하여 answer 리스트를 만든다.
def solution(n, build_frame):
answer = []
for frame in build_frame:
x,y,a,b = frame
if b==0: #삭제인 경우
answer.remove([x,y,a])
if not check(answer):
answer.append([x,y,a])
elif b==1: #설치인 경우
answer.append([x,y,a])
if not check(answer):
answer.remove([x,y,a])
return sorted(answer)마지막 정렬까지하여 반환하면 완료!
설치 시 검사하는 거 잘 만들어 두고 삭제하는데서 혼란이 와서 답지를 봐버리는 바보같은 실수를 했다. 그냥 반복해서 검사하면 된다는 생각을 해놓고 왜 삭제할땐 안쓴거지 ? 난 멍청인가 :<
함수 만들어서 쓰기 !제발
