[백준] N과M (1), (2), (3), (4) : 자바 백트레킹

이번 포스팅에서는 백준 N과 M 시리즈에 대해서 얘기해보자 ! 

문제 (2),(3),(4)는 (1)에 조건이 추가된 문제들이다. 

N과 M(1) 알고리즘을 풀어봤다면 (2),(3),(4) 는 비교적 쉽게 풀 수 있다.

✔️ N과 M (1) : 15649번

• arr : 출력할 수열을 담을 배열
• visited : 중복되지 않은 수를 출력하기 위해 방문 여부를 담을 배열

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

public class Main{
    static int[] arr;
    static boolean[] visited;
    private static StringBuilder result = 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까지의 수
        int n = Integer.parseInt(st.nextToken());
        //m 길이 만큼
        int m = Integer.parseInt(st.nextToken());

        arr = new int[n];
        visited = new boolean[n];
        dfs(n,m,0);
        System.out.println(result);
        }

    public static void dfs(int n, int m, int depth) {

        if(depth == m){
            for(int i  = 0; i<m; i++){
                result.append(arr[i]).append(' ');
            }
            result.append('\n');
            return;
        }

        for(int i = 0; i< n; i++){
            //해당 노드를 방문 하지 않았다면
            if(!visited[i]){
                visited[i] = true; //(= 같은 수를 출력하지 않기 위함 ex. 1,1)
                arr[depth] = i+1;
                dfs(n,m, depth+1);

                visited[i] = false;
            }
        }
    }


}

 

재귀 함수가 어떤 식으로 돌아가는지 손으로 써보면 이해하기 쉽다 !!

 

[알고리즘] 백트래킹이란? & 대표 문제: 백준 15679 N과M(1) - 자바

 

---

 

 

✔️ N과 M (2) : 15650 번

조건 : 고른 수열은 오름차순이어야 한다.

즉, 3,2 / 4,1 와 같은 수열은 출력하면 안된다. 

넣으려는 값과 직전에 넣은 값을 비교하면된다. 

 if(depth > 0 && arr[depth-1] > i+1) {
                continue;
            }

넣으려는 값은 i+1 이고 직전에 넣은 값은 arr[depth-1] 이 된다. 

만약 오름차순이 아니라면, i 를 증가시켜 arr에 값을 넣지 못하도록 continue 시켜 준다. 

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

public class Main{
    static int n,m;
    static int[] arr;
    static boolean[] visited;
    static StringBuilder result ;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //n까지의 수중에서
        n = Integer.parseInt(st.nextToken());
        //길이가 m인 수열을 구하자
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        visited = new boolean[n];
        result = new StringBuilder();

        dfs(0);
        System.out.println(result);
    }
    public static void dfs(int depth){

        if(depth == m){
            for(int i = 0; i<m; i++){
                result.append(arr[i]).append(' ');
            }
            result.append('\n');
            return;
        }

        for(int i = 0; i<n; i++){
            if(depth > 0 && arr[depth-1] > i+1) {
                continue;
            }
            if(!visited[i]){
                visited[i] = true;
                arr[depth] = i + 1;
                dfs(depth+1);
                visited[i] = false;
            }
        }
    }
}

 

---

 

✔️ N과 M (3) : 15651번

조건 : 같은 수를 여러 번 골라도 된다.

N과 M(1) 풀이 포스팅에서 얘기 했듯이,

visited 배열의 역할이 "같은 수를 여러 번 출력되지 않도록 하기 위함" 이였다.

따라서 visited 를 쓰지 않으면, 같은 수를 여러 번 고를 수 있다.

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

public class Main{
    static int n,m;
    static int[] arr;
    static boolean[] visited;
    static StringBuilder result ;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //n까지의 수중에서
        n = Integer.parseInt(st.nextToken());
        //길이가 m인 수열을 구하자
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        visited = new boolean[n];
        result = new StringBuilder();

        dfs(0);
        System.out.println(result);
    }
    public static void dfs(int depth){
        if(depth == m){
            for(int i = 0; i<m; i++){
                result.append(arr[i]).append(' ');
            }
            result.append("\n");
            return;
        }
        for(int i = 0; i<n; i++){
            arr[depth] = i+1;
            dfs(depth+1);
        }
    }
}

 

 

---

✔️ N과 M (4) : 15652번

조건 :

• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

이 문제는 N과 M(2)와 (3) 문제가 합쳐진 문제이다. 

 

1. visited 를 쓰지 않음으로 같은 수를 여러 번 고를 수 있다.

2. arr 배열에 값을 넣기 전에 검사한다.

if(depth >0 && arr[depth-1] > i+1){
                continue;
}

넣으려는 값과 직전에 넣은 값을 비교하여,

직전에 넣은 값이 더 크다면, i 를 증가시켜 arr에 값을 넣지 못하도록 continue 시켜 준다.

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

public class Main{
    static int n,m;
    static int[] arr;
    static boolean[] visited;
    static StringBuilder result ;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        //n까지의 수중에서
        n = Integer.parseInt(st.nextToken());
        //길이가 m인 수열을 구하자
        m = Integer.parseInt(st.nextToken());

        arr = new int[m];
        visited = new boolean[n];
        result = new StringBuilder();

        dfs(0);
        System.out.println(result);
    }
    public static void dfs(int depth){
        if(depth == m){
            for(int i = 0; i<m; i++){
                result.append(arr[i]).append(' ');
            }
            result.append("\n");
            return;
        }

        for(int i = 0; i<n; i++){
            if(depth >0 && arr[depth-1] > i+1){
                continue;
            }
            arr[depth] = i+1;
            dfs(depth+1);
        }
    }
}