[백준 17136] 색종이 붙이기

1. 문제

www.acmicpc.net/problem/17136

17136번: 색종이 붙이기

2. 접근 방법

백트래킹을 써야합니다. (그래도 python은 시간초과나서 pypy3로 풀었음 ㅜ)

 

1. board 탐색을 한다.

2. 숫자 1을 만날 경우

2-1. 1의 영역이 어느 정도 인지 확인한다. (붙일 수 있는 가장 큰 색종이의 크기 확인)

2-2. 가장 큰 사이즈의 색종이부터 붙여본다.

2-3. 현재 사용하려는 색종이의 사용 횟수를 확인하고

2-4. 만약 5회를 넘지 않았다면 색종이를 붙이고 -> 색종이 사용 횟수 갱신(색종이 붙였으니까)하고 -> 완탐 고고 -> 색종이 떼고-> 색종이 사용횟수 갱신(색종이 뗐으니까)

3. 숫자 0을 만날 경우

3-1. 계속 탐색 고고

 

'''

4. 완탐 시 줄바꿈은 x 좌표가 9를 넘어갔을 때 -> y좌표 줄바꿈 시켜줌 (+x좌표는 0으로 고고)

5. 마지막 지점에 도착했을 때, 현재 최솟값과 이번 색종이 붙였을 때의 결과를 비교해서 더 작은 것을 최솟값에 담아준다.

(주의) 마지막 지점을 (9, 9)로 해버리면 9, 9는 색종이 붙이는 로직도 못하고 바이바이니까 (0, 10)으로 해줬다. (9, 9)를 지나 (10, 9)가 되면 4번에 의해 (0, 10)이 되기 때문

6. 가지치기는 현재 count가 최솟값 count보다 클 때 바로 return

'''

 

4, 5, 6로직이 board 탐색시 바로 진행되어야하는 것이므로 

코드의 전체 흐름은

1 -> 4, 5, 6 -> 2, 3 이 됩니다

 

이거는 코드를 보면서 주석을 같이 보면 이해가 될 듯 싶슴다

3. 코드

python

def canAttach(_x, _y, size):
    for y in range(_y, _y + size):
        for x in range(_x, _x + size):
            if x < 0 or x >= 10 or y < 0 or y >= 10 or board[y][x] == 0:
                return False
    return True

# tf에 따라 붙이고, 떼고 하는 것 
# (tf에 0이 들어갈 때 색종이를 붙이는 로직이고, 1이 들어갈 때 색종이를 떼는 로직)
def attach(_x, _y, size, tf):
    for y in range(_y, _y + size):
        for x in range(_x, _x + size):
            board[y][x] = tf

def dfs(_x, _y, cnt):
    global ans

    # 완탐시 줄바꿈이 필요할 때
    if _x >= 10:
        _x -= 10
        _y += 1

    # 마지막 지점에 도착했을 때
    if (_x, _y) == (0, 10):
        ans = min(cnt, ans)
        return

    # 만약 count가 ans(현재 최소 값)보다 클 때
    if cnt >= ans:
        return

    maxSize = 0

    # 탐색하다가 색종이를 붙일 수 있는 지점을 만나면
    if board[_y][_x] == 1:
        # 붙일 수 있는 가장 큰 색종이의 크기
        for size in range(5, 0, -1):
            if canAttach(_x, _y, size):
                maxSize = size
                break
        # 가장 큰 사이즈의 색종이부터 붙여본다.
        for size in range(maxSize, 0, -1):
            # 현재 사용하려는 색종이의 사용 횟수가 5번을 넘지 않는다면
            if papers[size] > 0:
                # 색종이를 붙인다.
                attach(_x, _y, size, 0)
                # 색종이 사용 횟수 갱신
                papers[size] -= 1
                # 완탐 고고
                dfs(_x, _y, cnt+1)
                # 색종이를 뗀다
                attach(_x, _y, size, 1)
                # 색종이 사용 횟수 갱신
                papers[size] += 1

    # 색종이를 붙일 수 없는 지점이면 계속 탐색 고고
    else:
        dfs(_x+1, _y, cnt)

ans = 1e9
papers = [-1, 5, 5, 5, 5, 5]
board = [list(map(int, input().split())) for _ in range(10)]
dfs(0, 0, 0)
print(ans if ans < 1e9 else -1)

4. 마치며

로직은 생각보다 안복잡한데,

 

원래 주르르르르륵 코딩하다가

함수로 나눠서 하려니까 헷갈리고 ㅠ

 

사실은 가지치기가 아직도 손에 익지 않았습니다 ㅠ 나 자신 화이팅

 

참고로 board의 값이 1일 때만 색종이의 크기를 확인하면 python으로도 풀리고, board 탐색할 때마다 색종이 크기 확인하면 pypy로 풀어야함다. !@!@!@!