2339 : 석판 자르기

문제

하나 이상의 불순물과 보석 결정체로 이루어진 석판을 여러 조각으로 나누어 가공해서, 보다 높은 가치를 얻을 수 있도록 만들려고 한다. 이때, 높은 가치의 석판을 만들기 위해서는 석판을 여러 조각으로 나누되, 각 조각에는 불순물이 없도록 해야하며, 보석 결정체도 단 하나씩만 포함하고 있어야 한다.

또한, 석판에서 불순물을 빼내기 위해서는 불순물을 포함하고 있는 지점을 중심으로 잘라야 되는데, 석판의 결 때문에 가로 또는 세로 방향으로만 석판을 자를 수 있다. 석판을 자를 때에는 이전에 자른 방향과 같은 방향으로는 자를 수 없다. (단, 처음에 자를 때는 가로방향이나, 세로방향 모두 가능하다.)

석판에 있는 불순물과 보석 결정체의 정보가 주어질 때, 이 석판에서 불순물들을 없애면서 석판을 나누되, 각 조각에 반드시 하나의 보석 결정체만이 들어 있도록 석판을 나누는 방법이 모두 몇 가지 존재하는지 계산하시오.

위의 그림은 초기 석판의 상태에서 불순물을 제거하면서 석판을 잘랐을 때, 최종적으로 나뉘어진 석판의 모습이다. 회색 선은 불순물을 중심으로 가로 또는 세로 방향으로 자른 경계선이고, 노란 색은 보석을 하나씩만 포함하고 있는 석판이다. 석판을 자를 때 ②번이나 ③번은 이전에 잘려진 방향, 즉 ①번의 방향과 같은 방향으로 자를 수 없으며, ④ 번도 마찬가지로 ②번과는 같은 방향으로 자를 수 없다. 단순하게 자르는 순서를 의미하는 것이 아니므로, ④번 방향이 ③번 방향과 같을 수도 있다.

잘라진 석판은 반드시 두 개의 석판이 나뉘어진 것이어야 한다. 또한 결정체가 있는 곳은 자를 수 없으며, 최종적으로 나뉘어진 석판에 두 개 이상의 결정체가 오면 안 된다.

입력

첫 번째 줄에는 석판의 크기 N(1 ≤ N ≤ 20)이 들어온다. 다음 줄부터 N줄에 걸쳐서 석판의 상태가 입력으로 들어온다. 여기서 1은 불순물을 의미하며, 2는 보석 결정체, 0은 불순물과 보석결정체가 존재하지 않는 곳을 의미한다. 이때, 보석 결정체의 수는 15개를 넘지 않으며, 각 줄에 주어지는 석판의 정보는 공백 하나로 구분한다.

---

출력

각각의 석판 안에 불순물이 없으면서 단 하나의 보석 결정체만이 있도록 주어진 석판을 나눌 때, 모두 몇 가지의 경우가 존재하는지를 출력하시오. 이때 가능한 경우가 존재하지 않으면 -1을 출력한다.

---

예제

8
0 0 0 0 0 2 0 0
0 0 0 0 0 0 1 0
0 0 2 1 0 0 2 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 2 1 0 0 0
0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0
>> 1 

---

풀이

# x의 start, y의 start, x의 end, y의 end , 이전에 자른 방향(가로or세로)
def cutting(x_st, y_st, x_ed, y_ed, prevRowCut):
    
    dirty = []  # 불순물
    dia = 0     # 보석
    
    for x in range(x_st, x_ed):
        for y in range(y_st, y_ed):
            if stones[x][y] == 1:
                dirty.append([x, y])
            elif stones[x][y] == 2:
                dia += 1
    
    if dia == 1 and len(dirty) == 0: return 1 # 제대로 석판 자름
    if dia == 0 or len(dirty) == 0 : return 0 # 잘못 자름

    count = 0   # 자르는 횟수

    if prevRowCut:							# 이전에 가로로 자름 -> 세로로 자르기
        for nx, ny in dirty:                # nx : 불순물의 x좌표
            can_cut = True                  # 자를 수 있는 여부
            for i in range(y_st, y_ed):
                if stones[nx][i] == 2:		# 불순물이 있는 nx줄에 y 중 보석 있음 -> 자르기 불가
                    can_cut = False
                    break
            if can_cut:                     # 불순물이 있는 nx줄에 있는 y 중 보석 없음
                count += (cutting(x_st, y_st, nx, y_ed, False) * cutting(nx + 1, y_st, x_ed, y_ed, False)) 
                # x줄의 end 지점을 nx로 변경 / x줄의 start 지점을 nx+1로 변경
                # 현재 세로로 석판을 잘랐음으로, prevRowCut 을 False 로 변경
                # count += 왼쪽 석판에서 나온 count * 오른쪽 석판에서 나온 count

    if prevRowCut != True:
        for nx, ny in dirty:                # ny : 불순물의 y좌표
            can_cut = True
            for i in range(x_st, x_ed):
                if stones[i][ny] == 2:  	# 불순물이 있는 ny줄에 x 중 보석 있음 -> 자르기 불가
                    can_cut = False
                    break
            if can_cut:                 	# 불순물이 있는 ny줄에 있는 x 중 보석 없음
                count += (cutting(x_st, y_st, x_ed, ny, True) * cutting(x_st, ny + 1, x_ed, y_ed, True))

    return count

from sys import stdin
N = int(stdin.readline())

stones = [list(map(int, input().split())) for _ in range(N)]

result = cutting(0, 0, N, N, -1)
print(result if result != 0 else -1)

• 처음에 자를 때는 가로방향이나, 세로방향 모두 가능

  • prevRowCut = -1 로 초기화
  • if prevRowCut 과 if prevRowCut != True 2개의 if 문 모두 실행
  • Python 에서 0이 아닌 값은 True 로 간주함
  • if not prevRowCut 은 False(0)일 때만 참(True)이 되므로, 해당 if 문 실행 불가함으로 사용 안함

• 가로 자르기 중 불순물이 있는 지점의 좌표가 nx 일때

  • x줄 end를 end로 설정 후 재귀 호출
  • x줄 start를 nx +1 로 설정 후 재귀 호출