[BOJ] 15684 - 사다리 조작
문제링크
문제설명
문제풀이
시도 1
시도 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)
Author And Source
이 문제에 관하여([BOJ] 15684 - 사다리 조작), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@woo0_hooo/BOJ-15684-사다리-조작저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)