[백준] 15684 사다리 조작

---

사다리 게임에 주어진 사다리에 가로선을 추가하여 i번째 사다리 게임의 결과가 i가 나오도록 하는 문제이다.

 

문제 자체는 백트래킹 알고리즘으로 간단히 해결할 수 있다. 하지만 시간, 메모리 제한을 고려하여 최적화 해야한다.

 

사다리를 배열로 치환하고 (r, c)에 사다리가 있을 경우 1 또는 True, 없을 경우 0 또는 False로 표시한다. 그리고 사다리를 놓으며 따라 내려간다. 만약 i가 (i, c)에서 사다리를 만날 경우 i = i + 1, (i-1, c)에서 만날경우 i = i - 1을 수행한다.

 

반복마다 사다리를 타고 내려가 임의의 i에 대해서 결과가 i가 나오는지 확인한다.

 

 

	from sys import stdin
	readline = stdin.readline
	def dfs(cnt, start_r, start_c):
	global ans
	if all_n_n():
	ans = min(ans, cnt)
	return
	# 종료 조건
	if cnt == 3 or ans <= cnt:
	return
	for r in range(start_r, H+1):
	# 이미 사다리가 놓여진 row의 다음 col에는 다리를 둘 수 없다.
	k = start_c if r == start_r else 1
	for c in range(k, N+1):
	if (c - 1 > 0 and ladder[r][c-1]) or (c + 1 < N and ladder[r][c+1]):
	continue
	if not ladder[r][c]:
	ladder[r][c] = True
	dfs(cnt + 1, r, c+2)
	ladder[r][c] = False
	def all_n_n():
	for c in range(1, N+1):
	cur = c
	for r in range(1, H+1):
	if cur > N or cur < 0: return False
	if ladder[r][cur]:
	cur += 1
	elif cur - 1 > 0 and ladder[r][cur-1]:
	cur -= 1
	if cur != c: return False
	return True
	if __name__ == "__main__":
	N, M, H = map(int, readline().split())
	ladder = [[False] * (N+1) for _ in range(H+1)]
	for _ in range(M):
	a, b = map(int, readline().split())
	ladder[a][b] = True
	ans = 4
	dfs(0, 1, 1)
	print(ans if ans < 4 else -1)

view raw BOJ15684.py hosted with ❤ by GitHub