[SW将校学校ジャングル]WEEK 01開発ログ-IV

フルナビゲーション

브루트-포스 알고리즘 구현

def bruteForce(p, t):
    i = 0 # t의 검색 인덱스
    j = 0 # p의 검색 인덱스
    while i < len(t) and j < len(p):
        if t[i] != p[j]:
            i -= j
            j = -1
        j += 1
        j += 1
    if j == len(p):
        return i - len(p)
    else:
        return -1

백트래킹 구현

void backtracking(int index){
    if(index==n){		# 탈출 조건
        return;
    }
    if(isPromising()){
        visited[index] = true;	# 상태변화
        backtracking(index+1);	# 재귀호출
        visited[index] = false;	# 상태복구
    }
}

bool isPromising(int index){	# 유망함수
    if(non-promising)
        return false;
    if(promising)
        return true;
}