문제링크

15684 - 사다리조작

문제설명

문제풀이

시도 1

dfs를 활용해서 백트래킹을 하려고 했다. 테케는 전부 맞게 나오는데 시간초과가 떴다 ^_ㅠ

import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline

N, M, H = map(int, input().split())
board = [[0] * N for _ in range(H)]
minval = 4
ladders = set()

for i in range(M):
    x, y = map(int, input().split())
    ladders.add((x-1,y-1))

def play(board):
    visited = [[0]*N for _ in range(H)]
    for i in range(N):
        cur_x, cur_y = 0, i
        visited[cur_x][cur_y] = 1
        while cur_x < H:
            if cur_y+1 < N and visited[cur_x][cur_y+1] != 1 and (cur_x, cur_y) in ladders:
                cur_y += 1
            elif cur_y-1 >= 0 and visited[cur_x][cur_y-1] != 1 and (cur_x, cur_y-1) in ladders:
                cur_y -= 1
            else:
                cur_x += 1
            if cur_x < H:
                visited[cur_x][cur_y] = 1
        if i != cur_y:
            return False
    return True

def dfs(count, board):
    global minval
    if count > 3:
        return
    
    if play(board):
        minval = min(minval, count)
        return

    for i in range(H):
        for j in range(N-1):
            if (i, j) not in ladders:
                if j-1 >= 0 and j+1 < N and (i, j-1) not in ladders and (i,j+1) not in ladders:
                    #사다리 설치
                    ladders.add((i,j))
                    dfs(count+1, board)
                    ladders.remove((i, j))
                elif j+1 < N and (i, j+1) not in ladders:
                    #사다리 설치
                    ladders.add((i,j))
                    dfs(count+1, board)
                    ladders.remove((i, j))
                elif j-1 >= 0 and (i, j+1) not in ladders:
                    #사다리 설치
                    ladders.add((i,j))
                    dfs(count+1, board)
                    ladders.remove((i, j))
dfs(0, board)

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

시도 2

대체 어디를 줄여야 할까,, 고민하다가 dfs도는 부분에서 매번 (0,0)부터 탐색하는게 아닌, 이전에 검사했던 부분 이후부터 탐색하도록 바꿨다. pypy3으로 아슬아슬하게 통과 ^_ㅠ

import sys
sys.setrecursionlimit(2000)
input = sys.stdin.readline

N, M, H = map(int, input().split())
board = [[0] * N for _ in range(H)]
minval = 4
ladders = set()

for i in range(M):
    x, y = map(int, input().split())
    board[x-1][y-1] = 1

def play(board):
    for start in range(N):
        cur_y = start
        for cur_x in range(H):
            if board[cur_x][cur_y] == 1:
                cur_y += 1
            elif cur_y > 0 and board[cur_x][cur_y-1] == 1:
                cur_y -= 1
        if start != cur_y:
            return False
    return True

def dfs(count, x, y):
    global minval
    if play(board):
        minval = min(minval, count)
        return
    if count == 3 or minval <= count:
        return
    for i in range(x, H):
        k = y if i == x else 0
        for j in range(k, N-1):
            if board[i][j] == 0 and board[i][j+1] == 0:
                board[i][j] = 1
                dfs(count+1, i, j+2)
                board[i][j] = 0
            
dfs(0, 0,0)

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