[백준 *Java] - N과 M 시리즈1,2 (15649,15650)

N과 M (1) 문제보기

15649번: N과 M (1)

N과 M (2) 문제보기

15650번: N과 M (2)

 

---

👇 접근방식 [내생각 정리]

이진트리로 그려보았습니다. 이 문제는 중복없이라는 말이 들어가서, 하나씩 탐색을 하고, 빽하고 다시 탐색하고.

이 과정을 반복하는데, N까지의 수를 1부터 차례대로 탐색을 하면 됩니다.

백트래킹 문제를 처음 접해서 먼저 개념을 공부했습니다. 

이 문제를 보고 완전탐색 방식으로 어떻게 접근할까 고민을 했지만, 설계하질 못했습니다 :(

먼저 다른 분 코드를 참고해서 어떻게 푸는 지 공부하면서 다시 풀었습니다.

---

https://devnuts.tistory.com/50

백트래킹(Backtracking) 이란?

 

그려본 이진트리로는 숫자 탐색하는 과정을 예제 입력 3번을 통해서 설명드리겠습니다.

booelan 배열을 준 뒤, 방문여부를 체크를 해주는게 중요합니다.

 

N이 1일 때, 경우를 가지고 설명을 하겠습니다.

1(T) - > 2(T) -> 3(T) -> 4(T,F) ->  3(F) ->  4(T) -> 3(T,F) -> 4(F) -> 2(F) -> 3(T) -> 2(T) -> 4(T,F) ->  2(F) -> 4(T) -> 2(T,F) ->  4(F) -> 3(F) -> 4(T) -> 2(T) - > 3(T,F) -> 2(F) ->  3(T) -> 2(T)

 

모든 총 과정은

true true true true 가 될 때, 값이 출력됩니다 이런식으로 길이가 M(4)이 되면 출력하게끔합니다. 

그러면 N이 1일 때, 

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2

이렇게 true가 되는 순으로 해당 N값이 들어가게 됩니다.

이제 남은 N이 2, 3, 4 일때의 값을 출력해주면 끝이나게 됩니다.

 

N과 M (1)

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

public class Main {

    static boolean[] visited;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    static void dfs(int N, int M, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!visited[i]) { // 방문 체크할 때, 중복확인을해서 숫자가 중복으로 나오지 않게끔 합니다.
                visited[i] = true;
                arr[depth] = i + 1;
                dfs(N, M, depth + 1); // 루프를 돌다가 M의 갯수가 4, 깊이가 4일 때 나오게되면서
                visited[i] = false;   // visited false 처리를 해줍니다.
            }
        }
    }

    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()); // 깊이

        arr = new int[M];
        visited = new boolean[N];
        dfs(N, M, 0); // N이 1부터 시작이고 +1 depth를 해주기 위해서 depth를 0으로 초기세팅합니다.
        System.out.println(sb);

    }
}

 

 

 

N과 M (2)

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

public class Main {

    static boolean[] visited;
    static int[] arr;
    static int N,M;
    static StringBuilder sb = new StringBuilder();

    static void dfs(int start, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }

        for (int i = start; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                arr[depth] = i + 1;
                //if (depth != 0 && arr[depth] < arr[depth-1]) continue;
                dfs(i + 1, depth+1); // 전체 루프를 도는 게 아닌, 미리 초기값을 설정해 줍니다.
                //dfs(N, M, depth + 1);
                visited[i] = false;
            }
        }
    }

    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];
        visited = new boolean[N];
        dfs(0, 0);
        System.out.println(sb);

    }
}