🔗
풀이
기둥과 보를 조건에 따라 설치하거나 제거할 수 있는지를 구현하는 문제이다. 구현의 난이도 자체는 어렵다고 할 순 없었지만 고려해야 할 게 많아서 까다로웠다.
각각의 위치에 대해 기둥과 보가 설치되어 있는지에 대한 정보가 필요하다. 특정 위치에서 위쪽으로는 기둥이 오른쪽으로는 보가 설치된다. 그렇다면 그 특정 위치에 2가지의 정보를 저장하면 될 것이다. 위치들은 2차원 배열로 구성되어 있고, 각 위치에 대해 [0, 0]과 같은 형식으로 정보를 저장하게 되면 3차원 배열이 되고, 설치가 되었을 때 1을 저장하면 된다.
먼저 기둥을 설치할 수 있는지부터 알아보자. 이건 배열로 저장되기 때문에 문제의 그림과는 반대로 아래쪽으로 설치된다. 설치하려는 기둥이 빨간색이라고 할 때, 이 기둥을 설치할 수 있는 조건은 다음과 같이 3가지이다.
(1) 바닥에 설치하는경우
(2) 아래쪽에 기둥이 존재하는 경우
(3) 아래쪽과 오른쪽 아래에 보가 존재하는 경우
if a == 0: # 기둥일 때
if y == 0: # 바닥일 때
return True
if x>0 and arr[y][x-1][1]: # 왼쪽 아래에 보가 설치되어 있을 때
return True
if y<n and arr[y][x][1]: # 아래에 보가 설치되어 있을 때
return True
if y>0 and arr[y-1][x][0]: # 아래에 기둥이 있을 때
return True같은 방식으로 보를 설치할 수 있는 경우는 다음과 같다.
(1) 아래쪽에 기둥이 있는 경우
(2) 오른쪽 아래에 기둥이 있는 경우
(3) 양 옆에 보가 존재하는 경우
기둥이나 보를 삭제해야 하는 경우는 조금 다르다. 현재의 아이템을 삭제했을 때, 삭제해도 주변의 기둥이나 보가 영향을 받지 않고 설치되어 있을 수 있는지를 확인해야 한다.
기둥을 삭제할 때 고려해야 하는 주변의 기둥과 보는 다음과 같다.
(1) 위쪽에 설치된 기둥
(2) 위쪽에 설치된 보
(3) 왼쪽 위에 설치된 보
보를 삭제해야 할 때 고려해야 하는 주변의 기둥과 보는 다음과 같다.
(1) 위쪽에 설치된 기둥
(2) 오른쪽 위에 설치된 기둥
(3) 양 옆에 설치된 보
삭제해야 하는 경우는 만약 위의 경우 중 하나라도 안 된다면 불가능하다. 어느 경우에도 해당하지 않는다면 통과한다.
def solution(n, build_frame):
def possible(x, y, a):
if a == 0: # 기둥일 때
if y == 0: # 바닥일 때
return True
if x>0 and arr[y][x-1][1]: # 왼쪽 아래에 보가 설치되어 있을 때
return True
if y<n and arr[y][x][1]: # 아래에 보가 설치되어 있을 때
return True
if y>0 and arr[y-1][x][0]: # 아래에 기둥이 있을 때
return True
else: # 보 일 때
if y>0 and arr[y-1][x][0]: # 아래에 기둥이 있을 때
return True
if y>0 and x<n and arr[y-1][x+1][0]: # 아래 오른쪽에 기둥이 있을 때
return True
if x>0 and x<n and arr[y][x-1][1] and arr[y][x+1][1]: # 양 옆에 보가 다 존재할 때
return True
return False
def remove_item(x, y, a):
arr[y][x][a] = 0
if a == 0: # 기둥일 때
if y<n and arr[y+1][x][0] and not possible(x, y+1, 0): # 위에 기둥이 있는데 얘 없으면 안 될 때
return False
if y<n and arr[y+1][x][1] and not possible(x, y+1, 1): # 내 위에 보가 있는데 나 없인 안 될 때
return False
if y<n and x>0 and arr[y+1][x-1][1] and not possible(x-1, y+1, 1): # 왼쪽 위에 보가 있는데 얘 없으면 안 될 때
return False
else:
if arr[y][x][0] and not possible(x, y, 0):
return False
if x<n and arr[y][x+1][0] and not possible(x+1, y, 0):
return False
if x>0 and arr[y][x-1][1] and not possible(x-1, y, 1):
return False
if x<n and arr[y][x+1][1] and not possible(x+1, y, 1):
return False
return True
arr = [[[0, 0] for _ in range(n+1)] for _ in range(n+1)]
for x, y, a, b in build_frame:
if b == 0:
if not remove_item(x, y, a):
arr[y][x][a] = 1
else:
if possible(x, y, a):
arr[y][x][a] = 1
result = []
for y in range(n+1):
for x in range(n+1):
if arr[y][x][0]:
result.append([x, y, 0])
if arr[y][x][1]:
result.append([x, y, 1])
result.sort()
return result