[알고리즘] 백트래킹(Backtracking)

개요

• 모든 경우의 수를 전부 고려하는 알고리즘
• 상태공간을 트리로 나타낼 수 있을 때 적합한 방식
• BFS는 큐의 크기를 고려해야하고 DFS는 트리의 깊이를 고려하여 선택
• 최단 거리의 경우 BFS가 유리

DFS

• 한 방향으로 진행하다가 끝에 다다르거나 더 진행해도 해가 없음이 확인되면 마지막 분기점으로 돌아가 다른 방향으로 진행을 반복
• 미로찾기, N-Queen

BFS

• 모든 분기점을 검사해가는 방식
• 가위바위보
  • 3가지 결과를 검사하고 각각 결과에 대해 3가지 결과를 검사
  • DFS를 쓰면 무한에 빠질 수도 있음

예제

• 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
  • 같은 수를 여러번 골라도 되는 경우에는 visited 조건 제외
  • Go

       package main
            
       import (
       	"bufio"
       	"fmt"
       	"os"
       )
            
       func dfs(writer *bufio.Writer, visited []bool, result []int, numberChoice, numberEnd, index int) {
       	if index == numberChoice {
       		for _, value := range result {
       			fmt.Fprintf(writer, "%d ", value)
       		}
       		fmt.Fprintf(writer, "\n")
            
       		return
       	}
            
       	for i := 1; i <= numberEnd; i++ {
       		if visited[i] {
       			continue
       		}
            
       		result[index] = i
            
       		visited[i] = true
       		dfs(writer, visited, result, numberChoice, numberEnd, index+1)
       		visited[i] = false
       	}
       }
            
       func main() {
       	reader := bufio.NewReader(os.Stdin)
       	writer := bufio.NewWriter(os.Stdout)
       	defer writer.Flush()
            
       	N := 0
       	M := 0
       	fmt.Fscanf(reader, "%d %d\n", &N, &M)
            
       	visited := make([]bool, N+1)
       	result := make([]int, M)
       	dfs(writer, visited, result, M, N, 0)
       }
    

• 자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 집합
  • 같은 수를 여러번 골라도 되는 경우에는 visited 조건 제외
  • Go

       package main
            
       import (
       	"bufio"
       	"fmt"
       	"os"
       )
            
       func dfs(writer *bufio.Writer, visited []bool, result []int, numberChoice, numberStart, numberEnd, index int) {
       	if index == numberChoice {
       		for _, value := range result {
       			fmt.Fprintf(writer, "%d ", value)
       		}
       		fmt.Fprintf(writer, "\n")
            
       		return
       	}
            
       	for i := numberStart; i <= numberEnd; i++ {
       		if visited[i] {
       			continue
       		}
            
       		result[index] = i
            
       		visited[i] = true
       		dfs(writer, visited, result, numberChoice, i, numberEnd, index+1)
       		visited[i] = false
       	}
       }
            
       func main() {
       	reader := bufio.NewReader(os.Stdin)
       	writer := bufio.NewWriter(os.Stdout)
       	defer writer.Flush()
            
       	N := 0
       	M := 0
       	fmt.Fscanf(reader, "%d %d\n", &N, &M)
            
       	visited := make([]bool, N+1)
       	result := make([]int, M)
       	dfs(writer, visited, result, M, 1, N, 0)
       }
    

• N-Queen
  • Go

       package main
            
       import (
       	"bufio"
       	"fmt"
       	"os"
       )
            
       func promising(board []int, currentRow int) bool {
       	for i := 0; i < currentRow; i++ {
       		if board[i] == board[currentRow] ||
       			i-currentRow == board[i]-board[currentRow] ||
       			(i-currentRow)*-1 == board[i]-board[currentRow] {
       			return false
       		}
       	}
            
       	return true
       }
            
       func dfs(board []int, currentRow, boardSize int, result *int) {
       	if currentRow == boardSize {
       		*result++
       	}
            
       	for i := 0; i < boardSize; i++ {
       		board[currentRow] = i
       		if promising(board, currentRow) {
       			dfs(board, currentRow+1, boardSize, result)
       		}
       	}
       }
            
       func main() {
       	reader := bufio.NewReader(os.Stdin)
       	writer := bufio.NewWriter(os.Stdout)
       	defer writer.Flush()
            
       	N := 0
       	fmt.Fscanln(reader, &N)
            
       	board := make([]int, 15)
            
       	result := 0
       	dfs(board, 0, N, &result)
            
       	fmt.Fprintln(writer, result)
       }