https://programmers.co.kr/learn/courses/30/lessons/60061
문제 설명
빙하가 깨지면서 스노우타운에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.
프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.
- 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
- 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
단, 바닥은 벽면의 맨 아래 지면을 말합니다.
2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다. 맨 처음 벽면은 비어있는 상태입니다. 기둥과 보는 격자선의 교차점에 걸치지 않고, 격자 칸의 각 변에 정확히 일치하도록 설치할 수 있습니다. 다음은 기둥과 보를 설치해 구조물을 만든 예시입니다.
예를 들어, 위 그림은 다음 순서에 따라 구조물을 만들었습니다.
- (1, 0)에서 위쪽으로 기둥을 하나 설치 후, (1, 1)에서 오른쪽으로 보를 하나 만듭니다.
- (2, 1)에서 위쪽으로 기둥을 하나 설치 후, (2, 2)에서 오른쪽으로 보를 하나 만듭니다.
- (5, 0)에서 위쪽으로 기둥을 하나 설치 후, (5, 1)에서 위쪽으로 기둥을 하나 더 설치합니다.
- (4, 2)에서 오른쪽으로 보를 설치 후, (3, 2)에서 오른쪽으로 보를 설치합니다.
만약 (4, 2)에서 오른쪽으로 보를 먼저 설치하지 않고, (3, 2)에서 오른쪽으로 보를 설치하려 한다면 2번 규칙에 맞지 않으므로 설치가 되지 않습니다. 기둥과 보를 삭제하는 기능도 있는데 기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다. 만약, 작업을 수행한 결과가 조건을 만족하지 않는다면 해당 작업은 무시됩니다.
벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.
열 번째 작업의 경우, (2, 2)에서 위쪽 방향으로 기둥을 세울 경우 조건을 만족하지 않으므로 무시됩니다.
나의 풀이
- 우선 기둥이나 보를 설치할 수 있는지 체크하는 함수를 먼저 구현했다.
def checkPillarInstall(x, y, coord_plane):
if y == 0:
return True
if coord_plane[x-1][y]["ceiling"] == True or coord_plane[x][y]["ceiling"] == True:
return True
if coord_plane[x][y-1]["pillar"] == True:
return True
return False
def checkCeilingInstall(x, y, coord_plane):
if coord_plane[x][y-1]['pillar'] == True or coord_plane[x+1][y-1]['pillar'] == True:
return True
if coord_plane[x-1][y]['ceiling'] == True and coord_plane[x+1][y]['ceiling'] == True:
return True
return False- 그리고 기둥이나 보를 삭제할 수 있는지 체크하는 부분을 고민했다. 첫번째로 시도한 것은 일일히 모든 조건을 직접 생각해 조건에 추가하는 것 이었다.
- 하지만 생각보다 경우의 수가 많아 구현하기 어려웠고 문제를 다시 읽다 힌트를 얻을 수 있었다.
문제 중
기둥과 보를 삭제한 후에 남은 기둥과 보들 또한 위 규칙을 만족해야 합니다.
여기서 위 규칙 은 기둥이나 보를 설치하기 위한 규칙이다. 즉 내가 구현해 놓은 기둥이나 보를 설치할 수 있는 함수를 활용해서 삭제가 가능한지 체크할 수 있었다.
1. 특정 보를 삭제할 경우
빨간색으로 표시한 보를 삭제할 경우, 파란색으로 표시한 보와 기둥들이 영향을 받는다. 즉 빨간색 보를 삭제했다고 가정하고, 파란색 보와 기둥을 설치할 수 있는지 체크한다. 이 때 하나라도 설치가 불가능하다면 빨간색 보는 삭제할 수 없다.
2. 특정 기둥을 삭제할 경우
위와 같은 방식으로 진행하며, 대신 영향을 받는 파란색 보와 기둥이 다르다.
코드
def solution(n, build_frame):
coord_plane = [ [ {"pillar":False, "ceiling":False} for _ in range(n+2) ] for _ in range(n+2) ]
answer = []
for build in build_frame:
x, y = build[0], build[1]
ceiling, install = build[2], build[3]
if install == 1:
if ceiling == 1:
if checkCeilingInstall(x, y, coord_plane):
coord_plane[x][y]['ceiling'] = True
else:
if checkPillarInstall(x, y, coord_plane):
coord_plane[x][y]['pillar'] = True
else:
if ceiling == 1:
if checkDel(x, y, coord_plane, "ceiling"):
coord_plane[x][y]['ceiling'] = False
else:
if checkDel(x, y, coord_plane, "pillar"):
coord_plane[x][y]['pillar'] = False
for x in range(n+1):
for y in range(n+1):
if coord_plane[x][y]['pillar'] == True:
answer.append( [x, y, 0] )
if coord_plane[x][y]['ceiling'] == True:
answer.append( [x, y, 1] )
return answer
def checkPillarInstall(x, y, coord_plane):
if y == 0:
return True
if coord_plane[x-1][y]["ceiling"] == True or coord_plane[x][y]["ceiling"] == True:
return True
if coord_plane[x][y-1]["pillar"] == True:
return True
return False
def checkCeilingInstall(x, y, coord_plane):
if coord_plane[x][y-1]['pillar'] == True or coord_plane[x+1][y-1]['pillar'] == True:
return True
if coord_plane[x-1][y]['ceiling'] == True and coord_plane[x+1][y]['ceiling'] == True:
return True
return False
def checkDel(x, y, coord_plane, delType):
if delType == "ceiling":
coord_list = [ (x-1, y, "ceiling"), (x, y, "pillar"), (x, y-1, "pillar"),
(x+1, y, "pillar"), (x+1, y, "ceiling"), (x+1, y-1, "pillar") ]
else:
coord_list = [ (x-1, y+1, "ceiling"), (x, y+1, "ceiling"), (x, y+1, 'pillar') ]
original = coord_plane[x][y][delType]
coord_plane[x][y][delType] = False
result = True
for cx, cy, category in coord_list:
if coord_plane[cx][cy][category]:
if category == "ceiling":
if checkCeilingInstall(cx, cy, coord_plane) == False:
result = False
break
else: # pillar
if checkPillarInstall(cx, cy, coord_plane) == False:
result = False
break
coord_plane[x][y][delType] = original
return result