백트랙킹

백트랙킹

하나씩 진행해보다가 맞지 않으면 뒤로 돌아가 다시 확인 반복

문제1) 미로탈출문제(지도x)

남쪽과 동쪽 두가지 방향으로만 갈 수 있다고 가정
이동하면서 갈 수 있는 곳을 확인

만약 막히게 된다면 왔던 곳을 다시 되돌아간다

장: 어떻게든 목적지에 도달 할 수 있다.
단: 최악의 경우에 도달 할 수도 있다

슈도코드

nxn크기라 가정시 목적지는 (n-1,n-1)라 가정

find_way(x,y): #현재 (x,y)칸에 서있다
	if x==n-1 and y=n-1 : return true
    if M[x][y] == safe: #빈칸확인
    	find_way(x+1,y) #남쪽으로 이동
        if try_down = True:
        	return True
        try-east = find_way(x,y+1)
        return try_east
    else:
    	return False # 막힌경우

문제2) N-Queens

nxn 체스판에 퀸을 놓는다
같은 열 대각선에 퀴이 있으면 안된다

x = [1,3,0,2] 이런식으로 x[0]에 1행에 놓여있는 퀸의 열번호를 적는다
이렇게 (0,0)부터 놔보고 다음 행에서 만족하는 곳 그다음 행에서 만족하는 곳을 찾는다

NQueens(k): #x[k]를 결정
	if k>=N: x[0] ... x[n-1]
		return
   	for c in range(N):
    	if queen can place at(k,c):
        	x[k] = c
        	NQueens(k+1)