[BOJ] 15684. 사다리 조작 (🥇, 구현)

lemythe423·2023년 6월 18일

풀이

단순하게 모든 칸들에 대해서 사다리를 놓아보는 완전탐색 방식으로 생각했는데 예상치 못한 중복 탐색이 발생해서 시간초과가 터졌다

풀이1(시간초과)

시간 줄여보겠다고 원래 사다리가 놓여있는 곳과 원래 놓여있지 않은 곳 두 가지에 대해서 따로 분기 처리를 해줬는데 이것 때문에 오히려 중복 탐색만 겁나게 발생했다

i번째에서 i번째로 가는 게 맞는지 확인하는 check 함수는 별 문제가 없었다.

n을 증가시켜가면서 그때마다 x, y를 구하는 방식은 좀 문제가 됐다. 만약 현재 위치에서 사다리를 놓게 되면 같은 행 바로 옆 칸에는 사다리를 놓을 수가 없는데, 다른 행이면 놓을 수 있게 되기 때문이다. 그거를 알려면 현재 행과 이전 행이 같은 행인지 아닌지를 판별할 수 있어야 하는데 단순히 n만 증가시켜서 dfs를 돌리게 되면 그걸 알게 되는게 까다로워졌다. 행과 열을 따로 처리해줘야 했다.

N, M, H = map(int, input().split())
ladder = [[0]*(N-1) for _ in range(H)]
minCnt = 4

for _ in range(M):
    a, b = map(int, input().split())
    ladder[a-1][b-1] = 1

def check():
    s = 0
    while s < N:
        t = s
        for i in range(H):
            if -1<t-1 and ladder[i][t-1]:
                t -= 1
            elif t < N-1 and ladder[i][t]:
                t += 1
        
        if t != s:
            return False
        s += 1
    return True

def putLadder(x, y):
    if (-1<y-1 and ladder[x][y-1]) or (y+1<N-1 and ladder[x][y+1]):
        return False
    return True

def manipulate(n, cnt, lst):
    global minCnt
    x, y = n // (N-1), n % (N-1)


    if n >= (N-1)*H or cnt > 3 or cnt > minCnt:
        return 
    
    if cnt < minCnt and check():
        print(lst)
        minCnt = cnt
        return 
    
    
    # 만약 아직 사다리가 세워져있지 않은 곳이라면
    # 이곳에 사다리를 세울 수 있는지 확인하고 사다리 세우기
    # (양 옆에 사다리가 없는 경우)
    if not ladder[x][y] and putLadder(x, y):
        ladder[x][y] = 1
        manipulate(n+1, cnt+1, lst+[(x, y)])
        ladder[x][y] = 0

    # 사다리 안 세우고 넘어가기
    manipulate(n+1, cnt, lst)

manipulate(0, 0, [])

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

풀이2

위의 블로그를 참고한 풀이

그냥 단순하게 생각해서 사다리가 없는 곳들에 대해서만 조합을 구한다고 생각하면 되는 문제였다. 사다리가 있는 것들에 대해서는 아예 고려를 안 하고 없는 것들만 모아놓고 그 중에서 0~3개를 선택해서 사다리를 놓는 문제이기 때문이다.

사다리가 있는 곳은 이미 있으니까 2칸 건너뛰고 놓는 방식으로 했고, 사다리가 없는 곳은 사다리를 놓았으면 2칸 건너뛰고 아니면 건너뛰지 않는 방식으로 했는데, 이때

(0, 0) : 사다리가 있는 곳 2칸 건너뛰기 -> (0, 2)
(0, 1) : 없는 곳에서 건너뛰지 않는 곳 -> (0, 2)

이렇게해서 중복이 발생했다. 대략 중복이 발생하지 않은 일반적 경우보다 2배이상 걸리는 것 같았고, H의 크기가 30만 돼도 90만의 계산이 발생한다고 하니 180만이면 시간초과가 뜰 만하다.

# 사다리 조작
import sys

def check():
    s = 0
    while s < N-1:
        t = s
        for i in range(H):
            if -1<t-1 and ladder[i][t-1]:
                t -= 1
            elif ladder[i][t]:
                t += 1
        
        if t != s:
            return False
        s += 1
    return True

def dfs(cnt, x, y):
    global minCnt
    print(x, y)
    if minCnt <= cnt:
        return 
    
    if check():
        minCnt = min(minCnt, cnt)
        return 
    
    if cnt == 3:
        return 
    
    for i in range(x, H):
        k = y if i == x else 0
        for j in range(k, N-1):
            if ladder[i][j] == 0:
                ladder[i][j] = 1
                dfs(cnt+1, i, j+2)
                ladder[i][j] = 0
            else:
                dfs(cnt, i, j+2)

N, M, H = map(int, input().split())
ladder = [[0]*N for _ in range(H)]
minCnt = 4

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    ladder[a-1][b-1] = 1

dfs(0, 0, 0)
print(-1 if minCnt == 4 else minCnt)