DFS 백트래킹

네! 정보처리기사 실기 스타일로 DFS와 백트래킹이 조합된 문제 코드와 자세한 해설을 포함해 만들어드릴게요.

---

문제 예시

1부터 N까지 수 중에서 M개를 고르는 모든 경우를 출력하는 문제 (중복 없이, 순서 상관 있음).
DFS + 백트래킹을 사용해서 구현.

---

전체 코드 (입력 포함)

import java.util.Scanner;

public class DFSBacktrackingExample {
    static int N;           // 1부터 N까지의 수
    static int M;           // 고를 개수
    static int[] selected;  // 현재 선택된 수 저장하는 배열
    static boolean[] used;  // 사용된 수인지 체크하는 배열

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

        // 1. N, M 입력 받기
        N = sc.nextInt();
        M = sc.nextInt();

        // 2. 선택 배열과 사용 체크 배열 초기화
        selected = new int[M];
        used = new boolean[N + 1];

        // 3. DFS 시작 (깊이 0부터 시작)
        dfs(0);

        sc.close();
    }

    // dfs 메서드: 현재 선택된 수의 개수(depth)를 매개변수로 받음
    static void dfs(int depth) {
        // 4. 종료 조건: M개를 다 고른 경우 출력
        if (depth == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(selected[i] + " ");
            }
            System.out.println();
            return;
        }

        // 5. 1부터 N까지의 수 중 아직 사용하지 않은 수를 고른다
        for (int i = 1; i <= N; i++) {
            if (!used[i]) {            // 아직 사용하지 않은 수인가?
                used[i] = true;        // 선택 표시
                selected[depth] = i;   // 현재 위치에 수 저장
                dfs(depth + 1);        // 다음 깊이 탐색
                used[i] = false;       // 백트래킹: 선택 취소
            }
        }
    }
}

---

코드 한 줄 한 줄 완전 해부 및 동작 예제 포함

1. import java.util.Scanner;

• 무슨 역할?: 사용자로부터 입력을 받기 위해 Scanner 클래스를 불러옴.
• 왜 여기?: Java 프로그램에서 외부 클래스를 사용할 때는 파일 상단에 import 해야 하므로 여기 있음.
• 실행 순서: 프로그램 실행 전에 컴파일러가 Scanner 클래스를 찾도록 함.

---

2. public class DFSBacktrackingExample {

• 무슨 역할?: 자바 프로그램의 클래스 정의 시작.
• 왜?: Java는 모든 코드를 클래스 안에 작성해야 하기 때문에 필요함.
• 실행 순서: 프로그램 시작 시 JVM이 이 클래스를 읽음.

---

3. static int N;

• 무슨 역할?: 1부터 N까지의 숫자 범위 상한을 저장할 변수.
• 왜 static?: main 메서드 및 static 메서드에서 공유하고 사용해야 해서.
• 예시: 사용자가 4 입력 시 N=4가 됨.

---

4. static int M;

• 무슨 역할?: 선택할 숫자의 개수를 저장할 변수.
• 왜 static?: 같은 이유로 main, dfs에서 접근 가능하게.
• 예시: 사용자가 2 입력 시 M=2.

---

5. static int[] selected;

• 무슨 역할?: 현재 고른 숫자들을 저장하는 배열.
• 왜?: 선택된 숫자들을 depth별로 기록해야 하므로.
• 예시: 선택 과정에서 [1, 3], [2, 4] 등 상태 저장.

---

6. static boolean[] used;

• 무슨 역할?: 1~N까지 숫자 중 사용된 숫자를 체크하는 배열.
• 왜?: 중복 선택 방지용.
• 예시: used[3] == true라면 3은 이미 선택된 상태.

---

7. public static void main(String[] args) {

• 무슨 역할?: 프로그램 실행의 시작점.
• 왜?: JVM이 프로그램 실행 시 제일 먼저 호출하는 메서드.
• 실행 순서: 가장 처음 실행됨.

---

8. Scanner sc = new Scanner(System.in);

• 무슨 역할?: 입력 받기 위한 Scanner 객체 생성.
• 왜 여기?: main 메서드 내에서 입력을 받을 준비.

---

9. N = sc.nextInt();

• 무슨 역할?: 사용자로부터 정수 N을 입력 받음.
• 왜?: 문제에서 숫자 범위를 지정해야 하니까.
• 예시: 입력: 4 → N=4 저장.

---

10. M = sc.nextInt();

• 무슨 역할?: 사용자로부터 정수 M을 입력 받음.
• 왜?: 고를 숫자 개수를 알아야 하니까.
• 예시: 입력: 2 → M=2 저장.

---

11. selected = new int[M];

• 무슨 역할?: M개의 선택된 숫자를 저장할 배열 생성.
• 왜 여기?: M의 값이 입력받은 후에 배열 크기를 정해야 하므로.
• 예시: M=2 → selected 배열 크기 2.

---

12. used = new boolean[N + 1];

• 무슨 역할?: 1~N 숫자 사용 여부를 저장할 boolean 배열 생성.
• 왜 N+1?: 인덱스 1부터 N까지 사용하기 위해 0번 인덱스는 비워둠.
• 예시: N=4 → used[0..4], used[1]=false 초기화 상태.

---

13. dfs(0);

• 무슨 역할?: 깊이 0부터 DFS(백트래킹) 탐색 시작.
• 왜?: 아직 숫자 0개 선택 상태에서 탐색 시작.
• 예시: 선택된 숫자 없고, 첫 번째 숫자를 고를 차례임.

---

14. static void dfs(int depth) {

• 무슨 역할?: 재귀 함수로, 현재까지 선택한 숫자 개수를 depth로 받음.
• 왜?: 선택 단계 구분 및 종료 조건 처리용.
• 예시: depth=0 → 첫 번째 숫자 고르는 상태.

---

15. if (depth == M) {

• 무슨 역할?: 종료 조건 검사, M개를 다 골랐는지 확인.
• 왜?: 다 골랐으면 결과 출력하고 재귀 종료해야 함.
• 실행 순서: 재귀 호출마다 검사됨.

---

16.

for (int i = 0; i < M; i++) {
    System.out.print(selected[i] + " ");
}
System.out.println();

• 무슨 역할?: 선택된 배열을 출력.
• 왜?: 문제 요구사항인 모든 경우 출력.
• 예시: selected = [1, 3] → 출력 "1 3"

---

17. return;

• 무슨 역할?: 재귀 함수 종료.
• 왜?: 더 이상 진행할 필요 없으므로 탐색 종료.

---

18.

for (int i = 1; i <= N; i++) {

• 무슨 역할?: 1부터 N까지 모든 숫자를 시도.
• 왜?: 가능한 모든 숫자 조합을 탐색해야 해서.
• 실행 순서: 선택하지 않은 숫자 중에서 고를 때마다 반복.

---

19. if (!used[i]) {

• 무슨 역할?: i가 아직 선택되지 않은 수인지 체크.
• 왜?: 중복 선택 방지를 위해.
• 예시: used[3]이 false이면 3 선택 가능.

---

20. used[i] = true;

• 무슨 역할?: 숫자 i를 선택 처리.
• 왜?: 재귀 호출 시 중복 방지.
• 실행 순서: 선택 후 재귀 호출 전.

---

21. selected[depth] = i;

• 무슨 역할?: 현재 깊이 위치에 숫자 i 저장.
• 왜?: 나중에 결과 출력 및 재귀 탐색 시 사용.
• 예시: depth=1, i=3 → selected[1] = 3.

---

22. dfs(depth + 1);

• 무슨 역할?: 다음 깊이 탐색을 위해 재귀 호출.
• 왜?: 숫자를 하나 고를 때마다 깊이가 1 증가.
• 예시: depth=0에서 depth=1로 재귀 이동.

---

23. used[i] = false;

• 무슨 역할?: 백트래킹, 선택했던 숫자 해제.
• 왜?: 다른 경우의 수를 탐색할 수 있도록 원상 복구.
• 예시: i=3 선택 후 탐색 종료 → 다시 used[3]=false.

---

실행 흐름 예제 (입력: N=3, M=2)

• 초기 상태: selected=[,], used=[false,false,false,false]

• dfs(0) 호출

  • i=1 선택: used[1]=true, selected[0]=1 → dfs(1)

    • i=1은 used[1]=true이므로 건너뜀

    • i=2 선택: used[2]=true, selected[1]=2 → dfs(2)

      • depth==M(2), 출력: "1 2"

      • 백트래킹: used[2]=false

    • i=3 선택: used[3]=true, selected[1]=3 → dfs(2)

      • depth==M(2), 출력: "1 3"

      • 백트래킹: used[3]=false

    • 백트래킹: used[1]=false

  • i=2 선택: used[2]=true, selected[0]=2 → dfs(1)

    • i=1 선택: used[1]=true, selected[1]=1 → dfs(2)

      • 출력: "2 1"

      • 백트래킹: used[1]=false

    • i=2는 used[2]=true → 건너뜀

    • i=3 선택: used[3]=true, selected[1]=3 → dfs(2)

      • 출력: "2 3"

      • 백트래킹: used[3]=false

    • 백트래킹: used[2]=false

  • i=3 선택: used[3]=true, selected[0]=3 → dfs(1)

    • i=1 선택: used[1]=true, selected[1]=1 → dfs(2)

      • 출력: "3 1"

      • 백트래킹: used[1]=false

    • i=2 선택: used[2]=true, selected[1]=2 → dfs(2)

      • 출력: "3 2"

      • 백트래킹: used[2]=false

    • i=3는 used[3]=true → 건너뜀

    • 백트래킹: used[3]=false

---

좋습니다! 아래는 위 코드 전체에 대한 실행 흐름 해설 + DFS + 백트래킹 개념을 예제와 함께 차근차근 "완전 디버깅 해설"로 설명해드리겠습니다.

---

📌 문제:

1부터 N까지의 수 중에서 M개를 중복 없이 고르는 모든 순열을 출력하라.

📌 입력 예시:

입력:
3 2

📌 기대 출력:

1 2
1 3
2 1
2 3
3 1
3 2

---

🌲 DFS + 백트래킹 구조 흐름 요약

1. DFS(깊이 우선 탐색) 으로 가능한 모든 숫자를 하나하나 고르며 내려감
2. M개를 고르면 출력하고 종료
3. 백트래킹으로 선택한 숫자를 되돌려서 다른 경우의 수를 다시 시도함
   → 이 과정을 반복

---

🎯 입력 분석

입력값: 3 2
→ N = 3, M = 2
→ 1, 2, 3 중에서 중복 없이 2개를 고르는 모든 순열

---

📘 변수 구성

변수명	설명	예시 (처음)
N	전체 숫자의 범위	3
M	몇 개를 고를지	2
selected[]	현재까지 선택된 숫자들을 담는 배열	[_, _]
used[]	숫자가 이미 선택됐는지 체크하는 배열	[F, F, F, F] (index 1~3 사용)

---

🧠 DFS 재귀 구조 설명 (입력: 3 2)

🔁 Step-by-step 디버깅 흐름

---

dfs(0) 호출

• 현재 depth = 0
• 아직 아무 숫자도 고르지 않음

반복문 시작 (i = 1부터 N = 3까지)

---

i = 1

• used[1] == false → 선택 가능
• used[1] = true, selected[0] = 1
• dfs(1) 재귀 호출

---

dfs(1) 호출

• 현재 depth = 1
• selected = [1, _]

반복문 시작 (i = 1~3)

• i = 1 → used[1] == true → 스킵

• i = 2 → used[2] == false

  • used[2] = true, selected[1] = 2
  • dfs(2) 호출

---

dfs(2) 호출

• depth == M → 정답 하나 완성됨
• selected = [1, 2] 출력
• 백트래킹: used[2] = false

---

돌아와서 i = 3

• i = 3 → used[3] == false

  • used[3] = true, selected[1] = 3
  • dfs(2) 호출

출력: 1 3

→ used[3] = false

→ 돌아감 → used[1] = false (1번 백트래킹 완료)

---

i = 2

• used[2] = false
• selected[0] = 2, used[2] = true
• dfs(1) 호출

---

dfs(1) (selected: [2, _])

• i = 1 → used[1] = false

  • selected[1] = 1, used[1] = true
  • dfs(2) → 출력: 2 1
  • 백트래킹: used[1] = false

• i = 3 → used[3] = false

  • selected[1] = 3, used[3] = true
  • dfs(2) → 출력: 2 3
  • 백트래킹: used[3] = false

• 백트래킹: used[2] = false

---

i = 3

• used[3] = false
• selected[0] = 3, used[3] = true
• dfs(1) 호출

---

dfs(1) (selected: [3, _])

• i = 1 → used[1] = false

  • selected[1] = 1, used[1] = true
  • dfs(2) → 출력: 3 1
  • 백트래킹: used[1] = false

• i = 2 → used[2] = false

  • selected[1] = 2, used[2] = true
  • dfs(2) → 출력: 3 2
  • 백트래킹: used[2] = false

• 백트래킹: used[3] = false

---

✅ 최종 출력 결과

1 2
1 3
2 1
2 3
3 1
3 2

---