[백준] 2339번 석판 자르기

사용 언어 - Python3

2339번: 석판 자르기 (골드1, DFS 백트래킹 문제)

문제 ★분할 정복 문제★

2339번: 석판 자르기

 

정답

석판을 자를 수 있을 때까지 분할하는 "분할 정복" 알고리즘

(백준에서 정답자의 풀이를 보고 이해했습니다)

x의 start, end 범위 설정 sx, ex

y의 start, end 범위 설정 sy, ey

 

#정답

def f(sx, sy, ex, ey, hv):
    noise = [] #불순물
    dia = 0 #보석결정체
    
    for i in range(sx, ex):
        for j in range(sy, ey):
            if stones[i][j] == 1:
                noise.append([i, j])
            elif stones[i][j] == 2:
                dia += 1

    if dia == 1 and len(noise) == 0: 
        return 1 #다이아만 한개 -> 한개로만 나뉨
    if dia == 0 or len(noise) == 0:
        return 0 #둘다 없으면 -> 나눌게 없음 0

    count = 0 #자르는 횟수

    if hv != 1:
        for nx, ny in noise: #불순물의 x,y 좌표
            can_cut = True #자를 수 있는 여부
            for i in range(sy, ey):
                if stones[nx][i] == 2: #불순물이 있는 x줄(nx)에 있는 y 중 다이아가 있는 경우 
                    can_cut = False
                    break #다이아 있는 줄은 자를 수 없기 때문
            if can_cut: #nx줄에 있는 y 중 다이아가 없는 경우
                count += (f(sx, sy, nx, ey, 1) * f(nx + 1, sy, ex, ey, 1)) 
                # ex를 nx로 업데이트해준다. sx를 nx+1로 업데이트해준다.
                # x는 검토를 완료했으니, hv를 1로 바꾸어 2가 아닌 밑의 if문을 검사해서 y줄을 검사해준다.
                # 총 count = 왼쪽 석판에서 나온 count * 오른쪽 석판에서 나온 count

    if hv != 2:
        for nx, ny in noise:
            can_cut = True
            for i in range(sx, ex):
                if stones[i][ny] == 2: #불순물이 있는 y줄(ny)에 있는 x 중 다이아가 있는 경우
                    can_cut = False
                    break
            if can_cut: #ny줄에 있는 x 중 다이아가 없는 경우
                count += (f(sx, sy, ex, ny, 2) * f(sx, ny + 1, ex, ey, 2))
                # ey를 ny로 업데이트해준다. sy를 ny+1로 업데이트해준다.

    return count


n = int(input())

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

result = f(0, 0, n, n, 0)

print(result if result != 0 else -1)

 

---

레퍼런스

• 백준에서 다른 사람 정답 풀이 보는 법

1. 문제를 맞춘다.

2. 숏코딩이나 채점 현황에서 코드 공개한 사람들의 언어가 파랗게 하이퍼링크가 되어있다. 링크를 클릭하면 정답을 볼 수 있다.

 

• 정답 깃허브

GitHub - yyeongeun/codingtest: 코딩테스트 공부

• 분할 정복 백준 문제 모음

분할 정복 단계