[백준 15649] N과 M (1)

https://www.acmicpc.net/problem/15649

---

문제

---

아이디어

1부터 N까지 수 중 중복없이 M개를 출력해야 하는 문제이다.

4 4	// N:4, M:4

 

위와 같은 입력일 때,

1 ~ 4 중 4개 숫자를 나열하는 모든 경우의 수를 출력하면 된다.

 

N이 4이므로, (1, 2, 3, 4) 중 맨 첫 자리를 1로 선택했을 때의 경우다. 다음 자리에 올 수 있는 숫자는 1을 제외한 3개.

 

이후 2를 선택했을 때, 다음 자리에 올 수 있는 숫자들이다.

 

위 방식을 보았을 때, DFS로 구현하면 쉽게 탐색이 가능하다. 그러나, 우리는 모든 경우의 수를 탐색해야 하므로, 아래와 같이 백트래킹 과정이 필요하다.

이를 위해 기존 DFS 방식에서 종료 조건과 백트래킹 과정을 수정했다.

static void dfs(int num) {
    // 문자열 크기가 M이랑 같으면 재귀 종료
    if(sb.length() == M) {
        // 숫자 사이 공백 추가
        for(int i=0; i<sb.length(); i++)
            System.out.print(sb.charAt(i) + " ");
        System.out.println();
        return;
    }

    for(int i=1; i<=N; i++) {
        if(!visited[i]) {
            visited[i] = true;
            sb.append(i);

            dfs(num+1);
            // 백 트래킹
            visited[i] = false;
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

 

위 사진의 동작과정은 다음과 같다.

 

ex ) "1 2 3 4"

• sb : "1234"
• visited 배열

0	1	2	3	4
false	true	true	true	true

 

                                    ⬇️

 

sb.length() == 4 이므로, 출력 후 재귀 종료

 

                                    ⬇️

visited[i] = false;
sb.deleteCharAt(sb.length()-1);

 

                                    ⬇️

• sb : "123"
• visited 배열

0	1	2	3	4
false	true	true	true	false

 

                                    ⬇️

• sb : "12"
• visited 배열

0	1	2	3	4
false	true	true	false	false

 

                                    ⬇️

i = 4)

• sb : "124"
• visited 배열

0	1	2	3	4
false	true	true	false	true

 

.

.

.

 

위와 같이 재귀가 종료되면 추가했던 숫자를 제거해줌으로써 다음 인덱스로의 탐색을 이어나갈 수 있음.

---

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B_15649 {
    static int N, M;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N, M 입력
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        visited = new boolean[N + 1];

        dfs(0);
    }

    static void dfs(int num) {
        // 문자열 크기가 M이랑 같으면 재귀 종료
        if(sb.length() == M) {
            // 숫자 사이 공백 추가
            for(int i=0; i<sb.length(); i++)
                System.out.print(sb.charAt(i) + " ");
            System.out.println();
            return;
        }

        for(int i=1; i<=N; i++) {
            if(!visited[i]) {
                visited[i] = true;
                sb.append(i);

                dfs(num+1);
                // 백 트래킹
                visited[i] = false;
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }
}