알고리즘: 백트래킹(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)
        }