백준-15684-사다리 조작

문제

사다리 조작

풀이

문제조건 해석

사다리게임의 주어진 조건을 만족하도록 추가해야 하는 사다리 개수의 최소값을 구하는 문제

사다리 개수 <= 3 일 때까지 사다리를 놓을 수 있는 모든 경우의 수 구한 뒤 최소값 찾아야 한다.(완전탐색)

python으로는 시간초과 났다. pypy로 성공했다.

알고리즘

모든 경우의 수는 $O((N*H)^3)$ 약 27000000

1. 완전탐색은 DFS로 구현
2. 경우의 수 찾을 때 불가능한 조건 가지치기 해줘야 시간초과 나지 않는다.
3. 2차원 배열 deepcopy()하지 않고 stack으로 재귀 진입 전 사다리 놓아주고, 재귀 빠져나올 떄 되돌려준다.
   1. deepcopy()는 배열 크기만큼 시간복잡도, 공간복잡도가 늘어난다.
4. 사다리 놓을 수 있는 경우 찾는 반복문에서, 시작 인덱스를 지정해서 중복되지 않도록 해야한다.

코드

from sys import stdin
input = stdin.readline

n, m, h = [int(x) for x in input().rstrip().split()]
ladder = [[0 for _ in range(n)] for __ in range(h)]
for _ in range(m):
    a, b = [int(x) for x in input().rstrip().split()]
    ladder[a-1][b-1] = 1


def run():
    """
    모든 i번 세로선의 결과가 i이면 True 반환
    """
    for col in range(n):
        j = col
        i = 0
        while i < h:
            if j < n and ladder[i][j]:
                j += 1
            elif j > 0 and ladder[i][j-1]:
                j -= 1
            i += 1
        if j != col:
            return False
    return True


# 모든 추가할 수 있는 가로선 개수는 3개 이하
# O((N*H)^3) 약 27000000
def add_vertical(queue=[]):
    global answer
    level = len(queue)

    if run():  # 성공하면
        if level < answer:
            answer = level
        if queue:
            i, j = queue.pop()  # 사다리 놓았던 가로줄 되돌리기
            ladder[i][j] = 0
        return

    if level == 3:  # 가로선 개수 3개이면
        i, j = queue.pop()
        ladder[i][j] = 0
        return
    # 시작 인덱스 찾기
    if queue:
        si = queue[-1][0]
    else:
        si = 0

    for i in range(si, h):
        if i == si and queue:  # 시작 인덱스 찾기
            sj = queue[-1][1]
        else:
            sj = 0
        for j in range(sj, n-1):
            if not ladder[i][j]:  # 사다리 놓여있지 않고
                if j == 0:
                    if not ladder[i][j+1]:
                        ladder[i][j] = 1
                        queue.append((i, j))
                        add_vertical(queue)
                elif j == n-1:
                    if not ladder[i][j-1]:
                        ladder[i][j] = 1
                        queue.append((i, j))
                        add_vertical(queue)
                else:
                    if not ladder[i][j-1] and not ladder[i][j+1]:
                        # 놓을 사다리가 연속해서는 안된다
                        ladder[i][j] = 1
                        queue.append((i, j))
                        add_vertical(queue)
    # 더이상 사다리 놓을 곳 없으면 되돌리기
    if queue:
        i, j = queue.pop()
        ladder[i][j] = 0
    return


answer = 4
add_vertical()

if answer == 4:
    print(-1)
else:
    print(answer)

배운점

• 완전탐색에서는 가지치기(최적화) 제대로 해줘야 시간초과 피할수 있다.
• 재귀에서 배열의 값을 바꾸는 경우, stack을 따로 설정해줘서 재귀 진입 시에 바꿔주고, 반환 시에 스택에서 꺼내서 되돌려준다.