[알고리즘] 백트래킹(Backtracking)이란? (백준 15652, 9663)

📌 핵심 요약

• 백트래킹 — 선택 → 재귀 → 취소를 반복하며 모든 경우를 탐색하되, 조건 불만족 시 가지치기(Pruning)하는 기법
• N과 M (4) · 백준 15652 — 중복을 허용하는 비내림차순 수열, dfs(depth+1, i)로 같은 수 재선택 허용
• N-Queen · 백준 9663 — 1차원 배열 queen[row]=col로 퀸 위치 관리, 열·대각선 충돌을 isValid()로 가지치기

 

목차

 

1 백트래킹이란?

백트래킹(Backtracking)은 모든 경우의 수를 탐색하되, 불필요한 경우는 미리 제거(가지치기)하는 알고리즘 기법입니다.

완전 탐색(Brute Force)에 가지치기를 더한 것이라고 생각하면 됩니다.

핵심 동작 원리

백트래킹은 다음 세 단계를 반복합니다.

1. 선택(Choose) — 현재 상태에서 가능한 선택지 중 하나를 고른다
2. 재귀(Explore) — 선택한 상태로 다음 단계를 재귀 탐색한다
3. 취소(Unchoose) — 탐색이 끝나면 선택을 되돌리고 다른 선택지를 시도한다

ℹ️

가지치기(Pruning)란?

현재 상태에서 더 이상 유효한 답이 나올 수 없다고 판단되면 해당 가지를 탐색하지 않고 즉시 되돌아오는 것입니다. 이를 통해 탐색 공간을 획기적으로 줄일 수 있습니다.

일반적인 코드 구조

 

Java — 백트래킹 기본 구조

static void dfs(int depth) {
    // 종료 조건: 원하는 깊이에 도달하면 결과 처리
    if (depth == target) {
        process();
        return;
    }

    for (int i = 0; i < candidates; i++) {
        if (!isValid(i)) continue; // 가지치기

        choose(i);       // 선택
        dfs(depth + 1); // 재귀
        unchoose(i);    // 취소 (백트래킹)
    }
}

2백준 15652 — N과 M (4) 풀이

백준 #15652

N과 M (4)

1 ≤ M ≤ N ≤ 8 · 시간제한 1초

난이도: Silver III

1부터 N까지 자연수 중에서 M개를 고른 수열을 출력합니다. 같은 수를 여러 번 골라도 되며, 고른 수열은 비내림차순이어야 합니다. (앞 수 ≤ 뒷 수)

풀이 과정

1. 중복을 허용하므로 visited[]는 필요 없습니다.
2. 비내림차순을 위해 start 파라미터로 현재 선택한 숫자 이상만 다음에 고를 수 있게 합니다.
3. dfs(depth+1, i+1)이 아닌 dfs(depth+1, i)로 넘겨 같은 수의 재선택을 허용합니다.
4. depth == M이 되면 arr[]에 담긴 수열을 출력합니다.

전체 코드

 

Java — 백 15652

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        arr = new int[m];

        dfs(0, 1);
        System.out.print(sb);
    }

    static void dfs(int depth, int start) {
        if (depth == m) {
            for (int i = 0; i < m; i++) {
                sb.append(arr[i]);
                if (i < m - 1) sb.append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = start; i <= n; i++) {
            arr[depth] = i;
            dfs(depth + 1, i); // i+1이 아닌 i → 같은 수 재선택 허용
        }
    }
}

동작 흐름 (N=3, M=2)

 

트리 구조

dfs(0, 1)
 ├─ i=1 → dfs(1, 1)
 │         ├─ i=1 → 출력 "1 1"  ✅ 같은 수 허용
 │         ├─ i=2 → 출력 "1 2"
 │         └─ i=3 → 출력 "1 3"
 ├─ i=2 → dfs(1, 2)
 │         ├─ i=2 → 출력 "2 2"  ✅ 같은 수 허용
 │         └─ i=3 → 출력 "2 3"
 └─ i=3 → dfs(1, 3)
           └─ i=3 → 출력 "3 3"  ✅ 같은 수 허용

⚠️

i+1 vs i — 한 글자 차이의 큰 의미

dfs(depth+1, i+1)은 현재 고른 수보다 큰 수만 다음에 선택 가능 (오름차순, 15650).
dfs(depth+1, i)는 현재 고른 수와 같거나 큰 수를 선택 가능 (비내림차순, 15652).

3백준 9663 — N-Queen 풀이

백 #9663

N-Queen

1 ≤ N < 15 · 시간제한 10초

난이도: Gold IV

N×N 크기의 체스판에 N개의 퀸을 서로 공격하지 못하게 배치하는 경우의 수를 구합니다. 퀸은 가로, 세로, 대각선 모든 방향을 공격합니다.

풀이 과정

1. N개의 퀸을 N×N에 배치하면 반드시 각 행에 퀸이 하나씩 있어야 합니다. 따라서 dfs(row)로 행 단위로 탐색합니다.
2. queen[row] = col로 row행에 col열에 퀸을 배치합니다. 1차원 배열로 관리하면 코드가 훨씬 간결해집니다.
3. isValid(row, col)에서 같은 열과 대각선 충돌을 검사해 가지치기합니다.
4. row == N이 되면 N개를 모두 배치한 것이므로 count++합니다.

충돌 체크 조건

현재 (row, col)에 퀸을 놓으려 할 때, 이전 행의 퀸 (i, queen[i])와 비교합니다.

체크 항목	조건	이유
같은 행	자동 방지	행 단위로 내려가므로 같은 행에 2개 배치 불가
같은 열	queen[i] == col	이전 퀸과 같은 열이면 충돌
대각선	Math.abs(queen[i]-col) == Math.abs(i-row)	행 차이 == 열 차이 이면 대각선

ℹ️

대각선 공식이 왜 행 차이 == 열 차이 인가요?

체스판에서 대각선 이동은 항상 행이 n 움직이면 열도 n 움직입니다.
예) (0,1) → (1,2) → (2,3) : 행 +1, 열 +1 → 차이 항상 같음
따라서 두 점의 행 차이와 열 차이가 같으면 반드시 대각선 관계입니다.
Math.abs()를 쓰는 이유는 오른쪽 아래 / 왼쪽 아래 두 방향 모두를 잡기 위해서입니다.

전체 코드

 

Java — 백준 9663

import java.util.*;

public class Main {
    static int n;
    static int[] queen;
    static int count = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        queen = new int[n];

        dfs(0);
        System.out.println(count);
    }

    static void dfs(int row) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                queen[row] = col;
                dfs(row + 1);
                // queen[row] 복구 불필요 — 다음 col에서 덮어쓰기 때문
            }
        }
    }

    static boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 같은 열 체크
            if (queen[i] == col) return false;
            // 대각선 체크: 행 차이 == 열 차이
            if (Math.abs(queen[i] - col) == Math.abs(i - row)) return false;
        }
        return true;
    }
}

동작 흐름 (N=4 일부)

 

트리 구조 (일부)

dfs(0)  → 0행에 퀸 놓기
 ├─ col=0 → queen[0]=0
 │   dfs(1)
 │    ├─ col=0 → 같은 열 ❌
 │    ├─ col=1 → 대각선 ❌
 │    ├─ col=2 → queen[1]=2
 │    │   dfs(2)
 │    │    ├─ col=1 → queen[2]=1
 │    │    │   dfs(3) → col=3 → queen[3]=3 → count++ ✅
 │    │    └─ col=3 → queen[2]=3
 │    │        dfs(3) → 모두 충돌 ❌
 │    └─ col=3 → queen[1]=3  ...
 └─ col=1 → queen[0]=1  ...

4 두 문제로 보는 백트래킹 비교

항목	N과 M (4) · 15652	N-Queen · 9663
탐색 단위	depth (고를 자리)	row (행 번호)
가지치기 조건	start 파라미터로 범위 제한	isValid() — 열·대각선 충돌 체크
상태 저장	int[] arr	int[] queen
백트래킹 방식	다음 for 루프에서 덮어쓰기	다음 for 루프에서 덮어쓰기
출력/결과	수열 자체를 출력	경우의 수(count)만 출력

💡

백트래킹 문제 접근 체크리스트

① 탐색 단위(depth/row)를 무엇으로 잡을지 결정한다
② 종료 조건(depth == M, row == N)을 명확히 한다
③ 가지치기 조건(visited, isValid, start)을 설계한다
④ 상태 복구(visited=false, 덮어쓰기)가 필요한지 확인한다

잘못된 내용이 있다면 지적부탁드립니다. 방문해주셔서 감사합니다.