[알고리즘] 사다리 조작

포인트

• 조합을 이용하여 원하는 값을 얻을 수 있는가?
• 문제의 조건은 자기가 시작한 곳에서 끝을 낼 수 있는가? 입니다. 또한 조합을 이용해서 이곳을 지나도 되는지 아닌지를 확인하면서 사다리를 이동하는 것을 구현할 수 있는가? 를 보는 것 같습니다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python

def move() -> int:
	for row in range(n):
		pointer = row  
		for col in range(m):
			if data[pointer][col]:  #
				pointer += 1
			elif data[pointer - 1][col]:
				pointer -= 1
		if row != pointer:
			return 0
	return 1


def go(cnt: int, index: int, r: int) -> None:
	global answer
	if cnt == r:
		if move():
			answer = cnt
		return
	
	# 열
	for col in range(index, m):
		# 행
		for row in range(n - 1):
			if data[row][col]:
				continue
			if row - 1 >= 0 and data[row - 1][col]:
				continue
			if row + 1 < n and data[row + 1][col]:
				continue
			data[row][col] = 1
			go(cnt + 1, col, r)
			data[row][col] = 0


n, k, m = map(int, input().split())
data = [[0] * m for _ in range(n)]

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

answer = 987654321
for r in range(4):
	go(0, 0, r)
	if answer != 987654321:
		print(answer)
		break
else:
	print(-1)