문제
접근
혼자 해결하지 못하고 해설을 보며 참고했다.
하나씩 설치 혹은 제거를 해보고 가능한 경우인지 확인하는 과정을 반복
처음에는 설치와 제거를 따로두고 확인하려고 했는데, 코드가 복잡해진다.
조건을 검사하지 않고 우선 설치 혹은 제거를 하고 난 후의 남은 결과를 이용해 조건을 검사해준다.
조건이 만족한다면 설치 혹은 제거가 성공적으로 끝난거고,
만족하지 않는다면 설치 혹은 제거를 하면 안되므로, 원래 상태로 돌려준다.
조건은 현재 설치 혹인 제거된 아이템이 기둥인지 보인지에 따라 다르게 진행한다.
기둥인 경우 :
- 가장 아래(y가 0)인 경우 항상 가능하다.
- 다른 기둥 위에 있으면 가능하다.
- 보의 한쪽 끝 위에 있으면 가능하다.
이 세가지 경우가 모두 아닐 경우 현재 상태는 불가능한 상태이다.
보의 경우 :
- 한쪽 끝이 기둥위에 있으면 가능하다.
- 양쪽 옆에 보가 설치되어 있으면 가능하다.
이 두 경우가 모두 아닐 경우 현재 상태는 불가능한 상태이다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def solution(n, build_frame):
result = set()
for x, y, a, build in build_frame:
item = (x, y, a)
if build == 0: #삭제
result.remove(item)
if isImpossible(result):
result.add(item)
else: #설치
result.add(item)
if isImpossible(result):
result.remove(item)
answer = map(list, result)
answer = sorted(answer, key = lambda x : (x[0], x[1], x[2]))
return answer
def isImpossible(result):
COL, ROW = 0, 1
for x, y, a in result:
if a == COL: #기둥
if y != 0 and (x, y-1, COL) not in result and (x-1, y, ROW) not in result and (x,y,ROW) not in result:
return True
else: #보
if (x, y-1, COL) not in result and (x+1, y-1, COL) not in result and not ((x+1, y, ROW) in result and (x-1, y, ROW) in result):
return True
return False