[백준 15649/Java] N과 M(1)

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

15649번: N과 M (1)

 

---

 

아직 백트래킹이 뭔지 잘 모르겠다. 개념은 이해했는데 이걸 코드로 어떻게 짜지

공부를 더 해야겠음

 

✨ 참고
https://80000coding.oopy.io/85650ea5-e541-4b12-9b86-a958a99b7533

 

---

 

📌 백트래킹

한정 조건에서의 모든 경우의 수를 확인함.

해를 찾는 도중 그 경로가 해가 아닐 것 같으면 되돌아감

DFS 사용

 

---

 

풀이

위와 같이 각 수가 중복되지 않는 모든 경우의 수를 따라가면 된다.

for문을 사용해서 1부터 N까지의 수를 차례대로 확인하고, 그 수가 수열에 포함되어 있지 않으면 새로 추가해줌 (--> 사전 순으로 출력 가능)

어떤 한 수를 탐색할 때마다 해당 노드의 자식 노드들을 확인할 재귀함수 작성함

수를 하나씩 탐색할 때마다 바로바로 StringBuilder에 추가해줬다가 마지막에 출력해줬다.

어떤 수의 자식 노드들을 탐색할 때, 그 이전 노드들을 저장할 StringBuilder도 새로 생성했음

 

코드

• 백트래킹 함수 (재귀함수)

// 최종 출력할 StringBuilder
static StringBuilder sb = new StringBuilder();

static void backtracking(int row, int N, int M, boolean[] isContain, StringBuilder seq) {
    if (row == M + 1) { // 가장 밑 노드까지 내려가면 줄바꿈
        sb.append(seq);
        sb.append('\n');
    } else {
        // for문을 돌며 1부터 N까지의 숫자 출력
        for (int i = 1; i <= N; i++) {
            if (isContain[i]) { continue; }

            // 앞서 나온 숫자들을 반복 출력하기 위함
            // for문 내 이전 i 값이 출력되지 않도록 새로 생성하는 것
            StringBuilder tmp = new StringBuilder(seq);

            if (row > 1) {
                tmp.append(' ');
            }
            isContain[i] = true;
            tmp.append(i);

            backtracking(++row, N, M, isContain, tmp);

            // 기존 위치로 돌아오면 해당 노드의 모든 자식 노드를 확인한 것
            // 따라서 해당 노드도 반환
            isContain[i] = false;
            row--;
        }
    }
}

 

• main 함수

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

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    // 수열에서 어떤 수가 포함 돼있는지 확인
    boolean[] isContain = new boolean[N+1];

    backtracking(1, N, M, isContain, new StringBuilder());

    System.out.println(sb);
}

 

• 전체

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

public class Main {
    // 최종 출력할 StringBuilder
    static StringBuilder sb = new StringBuilder();

    static void backtracking(int row, int N, int M, boolean[] isContain, StringBuilder seq) {
        if (row == M + 1) { // 가장 밑 노드까지 내려가면 줄바꿈
            sb.append(seq);
            sb.append('\n');
        } else {
            // for문을 돌며 1부터 N까지의 숫자 출력
            for (int i = 1; i <= N; i++) {
                if (isContain[i]) { continue; }

                // 앞서 나온 숫자들을 반복 출력하기 위함
                // for문 내 이전 i 값이 출력되지 않도록 새로 생성하는 것
                StringBuilder tmp = new StringBuilder(seq);

                if (row > 1) {
                    tmp.append(' ');
                }
                isContain[i] = true;
                tmp.append(i);

                backtracking(++row, N, M, isContain, tmp);

                // 기존 위치로 돌아오면 해당 노드의 모든 자식 노드를 확인한 것
                // 따라서 해당 노드도 반환
                isContain[i] = false;
                row--;
            }
        }
    }

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 수열에서 어떤 수가 포함 돼있는지 확인
        boolean[] isContain = new boolean[N+1];

        backtracking(1, N, M, isContain, new StringBuilder());

        System.out.println(sb);
    }
}