1. 풀이
조건에 맞게 구현하면된다.
설치할때는 설치할 수 있는지 조건을 만족하는지, 삭제할때는 삭제한 후에도 모든 기둥과 보가 존립할 수 있는지를 따지면 된다.
입력이 좌표평면에서 x,y로 주어지는데, 이를 행렬로 바꾸면 x가 r, y가 c, 즉 좌표평면을 시계방향으로 90도 회전했다고 생각하면 된다. 그리고 기둥,보 설치여부를 리스트 L을 통해서 관리했다
(L[r][c][a] : r행 c열의 a가 설치되어있으면 1, 설치안되어있으면 0, 보는 해당좌표의 아래방향, 기둥은 해당좌표의 우측방향)
즉 x행,y열의 0(기둥)을 설치하면 L[x][y][0]=1, 삭제하면 L[x][y][0]=0
x행,y열의 1(보)를 설치하면 L[x][y][1]=1, 삭제하면 L[x][y][1]=0 으로 나타내준다.
<설치>
설치하는것은 쉽다. 문제에 나온 조건대로 적절한 위치에 기둥 혹은 보가 하나라도 있으면 설치하면된다.
<삭제>
삭제하는 것이 어렵다. 해당 기둥 혹은 보를 삭제했을 때 영향을 받는 모든 블럭들이 존립가능한지를 확인해줘야 하기 때문이다.
처음에는 모든 삭제하지 못하는 경우를 일일이 다 구하려고 했다(소스코드1). 정말 엄청 복잡하다. 뭐가틀린지도 모르겠고 sample test case만 돌아간다.
따라서 생각해낸 방법이 일단 삭제를 하고, 해당 블럭을 삭제함으로서 영향을 받는(규칙을 어기게 될 수도 있는)블럭들을 모두 검사하는 것이다. 그리고 이를 위해 해당 블럭이 존재가능한지를 확인해주는 함수 removeCheak()를 만들어주었다.
즉 정리하면 아래와 같다
(1) 일단 삭제하라는 블럭을 삭제한다
if b==0:
#삭제하고
L[r][c][t]=0(2) 삭제한 블럭때문에 규칙을 어기게 되는 블럭들을 찾는다
(3) 블럭들을 모두 removeCheka()를 통해서 검사한다
#모두 존립가능하면 삭제
if removeCheak(r,c+1,0) and removeCheak(r-1,c+1,1) and removeCheak(r,c+1,1):
ans.remove([r, c, t])※ removeCheak(r,c,x) 에서 L[r][c][x]가 존재하지 않아도 True를 반환하는것에 유의. 블럭이 있는데 규칙을 위반하는것이 문제이지 블럭이 처음부터 없으면 위반할일도 없다.
(4) 검사결과 하나라도 불만족하는게 있으면 삭제한 블럭을 다시 붙인다.
#하나라도 불만족하면 다시 붙이기
else:
L[r][c][t] = 1
2. 소스코드
(1) 소스코드1 (모든 위반하는 경우의수 다찾기, 실패)
def second(L):
return L[1]
def solution(n, build_frame):
R=max(build_frame)[0]
C=max(build_frame,key=second)[1]
L=[[[0,0] for j in range(C+2)] for i in range(R+2)]
ans=[]
for build in build_frame:
#print(ans)
r,c,t,b=build
#print(build)
r+=1
c+=1
#있는데 건설하는 경우 or 없는데 삭제하는 경우는 통과
if (b==1 and L[r][c][t]) or (b==0 and L[r][c][t]==0):
continue
#기둥
if t==0:
#삭제
if b==0:
# 1.기둥이 있음
if L[r][c+1][0] and L[r-1][c+1][1]==0 and L[r][c+1][1]==0:
continue
# 2.기둥없는 보있음
elif L[r-1][c+1][1] and L[r-1][c][0]==0 and L[r][c+1][1]==0:
if 0<=r-2:
if L[r-2][c+1][1]==0:
continue
else:
L[r][c][t] = 0
ans.remove([r, c, t])
else:
continue
elif L[r][c+1][1] and L[r+1][c][0]==0 and L[r+1][c+1][1]==0:
continue
else:
L[r][c][t]=0
ans.remove([r,c,t])
#설치
else:
# 1.바닥
if c==1:
L[r][c][t]=1
ans.append([r, c, t])
# 2.기둥위
elif L[r][c-1][0]:
L[r][c][t]=1
ans.append([r, c, t])
# 3.보끝
elif L[r-1][c][1] or L[r][c][1]:
L[r][c][t]=1
ans.append([r,c,t])
#보
else:
#삭제
if b==0:
# 기둥이 있을때
if L[r+1][c][0] and L[r+1][c][1]==0 and L[r+1][c-1][0]==0:
continue
elif L[r][c][0] and L[r-1][c][1]==0 and L[r][c-1][0]==0:
continue
# 보가 잇을때
elif L[r+1][c][1] and L[r+1][c-1][0]==0:
if r+2<R+2:
if L[r+2][c-1][0]==0 :
continue
else:
L[r][c][t] = 0
ans.remove([r, c, t])
elif L[r-1][c][1] and L[r][c-1][0]==0 and L[r-1][c-1][0]==0:
if 0<=r-2:
if L[r-2][c][1]==0:
continue
else:
L[r][c][t] = 0
ans.remove([r, c, t])
else:
continue
else:
L[r][c][t]=0
ans.remove([r, c, t])
#설치
else:
# 1. 기둥있을때
if L[r][c-1][0] or L[r+1][c-1][0]:
L[r][c][t]=1
ans.append([r, c, t])
# 2. 양쪽에 보가있을때
elif L[r-1][c][1] and L[r+1][c][1]:
L[r][c][t]=1
ans.append([r, c, t])
ans.sort()
size=len(ans)
for i in range(size):
ans[i][0]-=1
ans[i][1]-=1
return ans
(1) 소스코드2 (성공)
def second(L):
return L[1]
#r,c의 kind가 존립할수 있는가?
def removeCheak(r,c,kind):
global L,R,C
if L[r][c][kind]==0:
return True
#기둥
if kind==0:
if (0<=r-1 and L[r-1][c][1]) or (0<=c-1 and L[r][c-1][0]) or (L[r][c][1]):
return True
else:
return False
#보
else:
if (0<=c-1 and L[r][c-1][0]) or (0<=c-1 and L[r+1][c-1][0]) or (0<=r-1 and L[r-1][c][1] and L[r+1][c][1]):
return True
else:
return False
def solution(n, build_frame):
global L,R,C
R=max(build_frame)[0]
C=max(build_frame,key=second)[1]
L=[[[0,0] for j in range(C+10)] for i in range(R+10)]
ans=[]
for build in build_frame:
#print(ans)
r,c,t,b=build
#print(build)
#있는데 건설하는 경우 or 없는데 삭제하는 경우는 통과
if (b==1 and L[r][c][t]) or (b==0 and L[r][c][t]==0):
continue
#기둥
if t==0:
#삭제
if b==0:
#삭제하고
L[r][c][t]=0
#모두 존립가능하면 삭제
if removeCheak(r,c+1,0) and removeCheak(r-1,c+1,1) and removeCheak(r,c+1,1):
ans.remove([r, c, t])
else:
L[r][c][t] = 1
#설치
else:
# 1.바닥
if c==0:
L[r][c][t]=1
ans.append([r, c, t])
# 2.기둥위
elif L[r][c-1][0]:
L[r][c][t]=1
ans.append([r, c, t])
# 3.보끝
elif L[r-1][c][1] or L[r][c][1]:
L[r][c][t]=1
ans.append([r,c,t])
#보
else:
#삭제
if b==0:
#삭제하고
L[r][c][t]=0
#모두 존립가능하면 진짜삭제
if removeCheak(r-1,c,1) and removeCheak(r,c,0) and removeCheak(r+1,c,0) and removeCheak(r+1,c,1):
ans.remove([r, c, t])
else:
L[r][c][t] = 1
#설치
else:
# 1. 기둥있을때
if L[r][c-1][0] or L[r+1][c-1][0]:
L[r][c][t]=1
ans.append([r, c, t])
# 2. 양쪽에 보가있을때
elif L[r-1][c][1] and L[r+1][c][1]:
L[r][c][t]=1
ans.append([r, c, t])
ans.sort()
return ans