[Algorithm/Java] 백준 백트래킹 - N과 M 시리즈

2025-07-12 9 분 소요

문제집 N과 M

🧠 선행 지식

백트래킹이란?

현재 상태에서 가능한 모든 선택지를 따라가며 정답을 찾는 탐색 방법

완전탐색의 일종
모든 후보를 고려하되, 불필요한 탐색은 가지치기(Pruning) 로 줄인다
모든 경우의 수를 고려해야 할 때 사용
예시
- 미연시 게임: 모든 루트(선택지)를 탐색
- 오목: 가능한 모든 수를 놓아보며 승리 여부 판단

백트래킹 구현 방식

빈 리스트에서 시작해서, 가능한 수를 하나씩 추가해 나간다.
이미 사용한 수는 제외한다.
조건을 만족하지 않으면 되돌아가며(Backtrack) 다른 선택지를 탐색한다.

즉, 상태를 넘나드는 방식으로 탐색하는 방식이다.

[참고] 상태공간 트리란?

문제를 풀기 위한 모든 경우의 수(상태)를 트리 형태로 나타낸 구조

루트: [] (초기 상태)
자식 노드: 어떤 수를 선택한 이후의 상태
리프 노드: 원하는 길이(M)를 만족하는 상태

📌 문제

N과 M (1)

자연수 N과 M이 주어졌을 때, 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제 🔗]

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

public class Main {
    static int n, m;
    static int[] arr; // 수열을 저장할 배열
    static boolean[] v; // 숫자 사용 여부 체크 배열

    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];
        v = new boolean[n + 1];

        dfs(0);
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == m) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }


        // 2. dfs 호출
        for(int j = 1; j <=n; j++){
            if(!v[j]){
                v[j] = true;

                arr[depth] = j; // 현재위치(depth)에 숫자 저장
                dfs(depth + 1); // 다음 단계로 이동 (재귀)

                v[j] = false; // 백트래킹
            }
        }
    }
}

N과 M (2)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제 🔗]

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.

이진탐색 DFS

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

public class Main {
    static int n, m;
    static int[] arr;

    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(1, 0);
    }

    static void dfs(int depth, int cnt) {
        // 1. 종료 조건
        if (cnt == m) {
            for (int i = 0; i < m; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        if (depth > n) return;

        // 2. dfs 호출
        arr[cnt] = depth;

        // 선택 o
        dfs(depth + 1, cnt + 1);

        // 선택 x
        dfs(depth + 1, cnt);
    }
}

FOR 루프 DFS

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

public class Main {
    static int n, m;
    static int[] arr;

    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);
    }

    static void dfs(int depth, int s) {
        // 1. 종료 조건
        if (depth == m) {
            for (int val : arr) {
                System.out.print(val + " ");
            }
            System.out.println();
            return;
        }

        // 2. dfs 호출
        for(int j=s; j<=n; j++){
            arr[depth] = j; // 현재 숫자 선택
            dfs(depth + 1, j + 1);
        }
    }
}

N과 M (3) - 중복 순열

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

⚠️ System.out.println을 사용하면 시간초과가 나기 때문에, StringBuilder을 사용해서 풀어야한다.

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);
        System.out.print(sb);
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == m) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        for(int j=1; j<=n; j++){
            arr[depth] = j;
            dfs(depth + 1);
        }
    }
}

N과 M (4)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

1부터 N까지 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.

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 s) {
        // 1. 종료 조건
        if (depth == m) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        for(int j=s; j<=n; j++){
            arr[depth] = j;
            dfs(depth + 1, j);
        }
    }
}

N과 M (5)

N개의 자연수와 자연수 M이 주어졌을 때, N개의 자연수 중에서 M개를 고른 수열을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] v;

    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[n];
        ans = new int[m];
        v = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dfs(0);

        System.out.print(sb);
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == m) {
            for(int j=0; j<m; j++){
                sb.append(ans[j]).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        for(int j=0; j<n; j++){
            if(!v[j]){
                v[j] = true;
                ans[depth] = arr[j];
                dfs(depth + 1);
                v[j] = false;
            }

        }
    }
}

N과 M (9)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

for 루프가 시작하기 전에 prev를 초기화 하여, 현재 깊이에서 중복된 숫자를 선택하는 것을 방지할 수 있다.
dfs가 호출될 때마다 prev 변수는 새롭게 생성되고 0으로 초기화된다.

![alt text](<../../../assets/images/2024/N과 M (9).jpg>)

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] v;

    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[n];
        ans = new int[m];
        v = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dfs(0);

        System.out.print(sb);
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == m) {
            for(int j=0; j<m; j++){
                sb.append(ans[j]).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        int prev = 0;
        for(int j=0; j<n; j++){
            if(!v[j] && prev != arr[j]) {
                prev = arr[j];
                v[j] = true;

                ans[depth] = arr[j];
                dfs(depth + 1);

                v[j] = false;
            }
        }
    }
}

LinkedHashSet을 사용해서 풀 수도 있다.

⚠️ 무조건 LinkedHashSet을 써야하는데, 순서를 그대로 유지하면서 중복 제거하려면 LinkedHashSet이 적합하기 때문이다.
- LinkedHashSet:
  - 입력한 순서 유지
  - Arrays.sort()로 만든 사전 순 그대로 출력됨
  - 수열이 숫자 오름차순처럼 보이게 하려면 LinkedHashSet을 사용하자
- TreeSet:
  - 자동 오름차순 정렬 (기본은 String 기준)
  - 숫자 “135”, “16” -> 출력: “135”, “16” -> (사전 순 깨짐)
  - 즉, “1” vs “1” → 다음 “3” vs “6” → “3”이 작으므로 “135”가 앞에 옴

참고 블로그 - 그냥 그냥 블로그

StringBuilder는 Set<String>에 직접 넣을 수 없다
- 출력만 할 거면 System.out.println(sb) 해도 상관없지만,
- Set<String>에 넣으려면 반드시 .toString()으로 문자열로 변환해야 한다.
- sb는 StringBuilder 타입이고, Set<String>은 String만 받기 때문이다.

👩‍💻 전체 코드

문자열은 내용(값) 비교, int[] 와 같은 배열이나 객체는 메모리 주소 기반으로 중복 판별
따라서 int 대신 문자열로 변환해 set에 저장

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] v;
    static LinkedHashSet<String> set = new LinkedHashSet<>();

    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[n];
        ans = new int[m];
        v = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dfs(0);

        for(String s:set){
            System.out.println(s);
        }
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == m) {
            StringBuilder sb = new StringBuilder();
            for(int j=0; j<m; j++){
                sb.append(ans[j]).append(" ");
            }
            set.add(sb.toString());
            return;
        }

        // 2. dfs 호출
        for(int j=0; j<n; j++){
            if(!v[j]){
                v[j] = true;

                ans[depth] = arr[j];
                dfs(depth + 1);

                v[j] = false;
            }
        }
    }
}

N과 M (10)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

N개의 자연수 중에서 M개를 고른 수열
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ … ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

![alt text](<../../../assets/images/2024/N과 M (10).jpg>)

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] v;

    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[n];
        ans = new int[m];
        v = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dfs(0, 0);

        System.out.print(sb);
    }

    static void dfs(int depth, int s) {
        // 1. 종료 조건
        if (depth == m) {
            for(int j=0; j<m; j++){
                sb.append(ans[j]).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        int prev = 0;
        for(int j=s; j<n; j++){
            if(!v[j] && prev != arr[j]) {
                prev = arr[j];
                v[j] = true;

                ans[depth] = arr[j];
                dfs(depth + 1, j + 1);

                v[j] = false;
            }
        }
    }
}

N과 M (11)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.

prev만 필요
v[], s 불필요

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] v;

    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[n];
        ans = new int[m];
        v = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dfs(0);

        System.out.print(sb);
    }

    static void dfs(int depth) {
        // 1. 종료 조건
        if (depth == m) {
            for(int j=0; j<m; j++){
                sb.append(ans[j]).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        int prev = 0;
        for(int j=0; j<n; j++){
            if(prev != arr[j]) {
                prev = arr[j];

                ans[depth] = arr[j];
                dfs(depth + 1);
            }
        }
    }
}

N과 M (12)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. [문제]

N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.

prev, s 필요
v[] 불필요

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

public class Main {
    static int n, m;
    static int[] arr;
    static int[] ans;
    static boolean[] v;

    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[n];
        ans = new int[m];
        v = new boolean[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        dfs(0, 0);

        System.out.print(sb);
    }

    static void dfs(int depth, int s) {
        // 1. 종료 조건
        if (depth == m) {
            for (int j = 0; j < m; j++) {
                sb.append(ans[j]).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 2. dfs 호출
        int prev = 0;
        for (int j = s; j < n; j++) {
            if (prev != arr[j]) {
                prev = arr[j];

                ans[depth] = arr[j];
                dfs(depth + 1, j);
            }
        }
    }
}

박시은

[Algorithm/Java] 백준 백트래킹 - N과 M 시리즈

🧠 선행 지식

백트래킹이란?

📌 문제

N과 M (1)

N과 M (2)

N과 M (3) - 중복 순열

N과 M (4)

N과 M (5)

N과 M (9)

N과 M (10)

N과 M (11)

N과 M (12)

댓글남기기

참고

[Algorithm/Java] 백준 2615번 - 오목

[Algorithm/Java] 백준 14620번 - 꽃길

[Algorithm/Java] 백준 6443번 - 에너그램

[Algorithm/Java] 백준 1799번 - 비숍