15650번, 15651번, 15652번

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

15650번: N과 M (2)

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

15651번: N과 M (3)

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

15652번: N과 M (4)

이번에는 부족하다고 느낀 백트레킹 부분의 DFS 문제를 같은 유형 3개를 풀어보았다.

내가 생각하기에 15650번이 나머지 두 문제보다 어려웠는데 왜 정답률이 제일 높은지 잘 모르겠지만, 먼저 이 문제를 풀어보겠다.

문제에서 주어진 출력은 아래의 사진과 같다.

보면 느낌이 오듯이 중복을 제외하고 오름차순으로 나열된 수열들이다.

따라서 중복이 없어야하고, 오름차순으로 되어있는 배열 조합을 찾아야한다.

그래서 코드를 짤때는 먼저 깊이에 따라 배열을 출력하는 로직을 구현한다. 

public void dfs(int at,int depth){
    if(depth==m){
        for(int i : arr){
            sb.append(i).append(" ");
        }
        sb.append("\n");
        return;
    }


    for(int i=at; i<=v; i++){
        if(depth>=1){
            if(arr[depth-1]<i){
                arr[depth]=i;
            }
        }else arr[depth]=at;
        dfs(at+1,depth+1);
        at++;
    }
}

위의 코드처럼 깊이가 주어진 M과 같으면 배열안에 모든 요소를 출력하도록 만든다. 그리고 그 다음에는 처음 시작하는 숫자가 커짐에 따라 for문의 범위를 커진 숫자의 값과 맞춰주는 것이다. 즉 시작 값이 1에서 시작해서 1로 시작하는 수열이 끝나면 2로 시작하는 수열을 찾아야하는데 여기서 1은 포함되어있어서는 안된다. 즉 4 2의 경우 2 2, 2 3, 2 4 만이 와야한다. 2 1은 오면 안된다. 그래서 arr안에 깊이에 따라 값이 오름 차순으로 되어있는지 확인하는 조건문을 추가해야한다. 여기서 주의해야 할 것은 깊이가 0일때이다. 깊이가 0일때는 예를 들어 4 2에서 1로시작하는 수열을 찾는 재귀함수에 들어가서 값을 증가시키면서 수열들을 찾아내고 나온다음에, 그 다음 2로 시작하는 수열을 찾으러 재귀함수에 들어가려면 깊이 0의 시작 값이 1에서 2로 바뀌어야한다. 그래서 at을 재귀함수 호출 후 증가시키는 것이다.

즉, 여기서 at은 두 가지 역할을 하는 것이다. 4 2를 입력했을 때 1 ->2->3->4로 증가하면서 1 2, 1 3, 1 4의 값을 찾아내는 용도와 그 다음 1->2로 증가하여 2 2, 2 3, 2 4 앞의 값을 바꾸는 두 가지 용도로 사용된다.

 

그 다음 15651번을 봐보자.

이 문제는 위의 15650번보다 훨씬 간단하다. 아래의 입출력을 보면 느낄 수 있을 것이다.

이 문제는 중복을 허용하고 오름차순을 요구하는 것도 아니기 때문에 그냥 출력하면 된다.

여기서는 at을 둘 필요도 없다.

그냥 dfs문을 돌리면 끝이다.

public void dfs(int depth){
    if(depth==m){
        for(int i : arr){
            sb.append(i).append(" ");
        }
        sb.append("\n");
        return;
    }
    for(int i=0; i<v; i++){
        arr[depth]=i+1;
        dfs(depth+1);
    }
}

다른 조건이 필요가 없는 아주 쉬운 문제였다. 이 문제부터 푸는 공부를 했어야했는데..

 

마지막으로는 15652번을 풀어보자.

이 문제는 중복을 허용하고, 오름차순으로 정렬하는 것이 조건이다.

즉, 15650번은 위의 15651번과 지금 문제를 풀줄 알면 풀리는 문제라고 느꼈다.

그래서 역시 이 문제는 15650번과 마찬가지로 at변수를 이용할 것이다.

여기서는 중복을 허용하기 때문에 재귀함수를 호출할때 at의 +1 값으로 넣지 않고, 현재의 값으로 넣을 것이다.

그렇게 되면 4 2의 경우 1 1, 1 2,1 3,1 4, 2 2, 2 3, 2 4로 될 것이다. 

public void dfs(int at, int depth){
    if(depth==m){
        for(int i : arr){
            sb.append(i).append(" ");
        }
        sb.append("\n");
        return;
    }
    for(int i=at; i<v; i++){
        arr[depth]=i+1;
        dfs(at,depth+1);
        at++;
    }
}

즉, 재귀함수 안에 넣는 at은 출력값의 뒤에 값들을 결정하고, 재귀 호출 후 증가 시키는 at은 첫번째 자리 수를 결정한다.

 

정답코드는 아래와 같다.

package backjoon;

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

public class b15650 {
    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());
        Graph1 g = new Graph1(N,M);
        g.dfs(1,0);
        System.out.println(g.sb);
    }
}
class Graph1{
    int v;

    int[] arr;

    int m;
    boolean[] visit;

    int count = 0;
    StringBuilder sb;
    public Graph1(int v, int m) {
        this.v = v;
        this.m = m;
        arr = new int[m];
        visit = new boolean[v];
        sb = new StringBuilder();
    }
    public void dfs(int at,int depth){
        if(depth==m){
            for(int i : arr){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }


        for(int i=at; i<=v; i++){
            if(depth>=1){
                if(arr[depth-1]<i){
                    arr[depth]=i;
                }
            }else arr[depth]=at;
            dfs(at+1,depth+1);
            at++;
        }
    }
    public void dfs2(int depth){
        if(depth==m){
            for(int i : arr){
                System.out.println(i);
            }
            System.out.println();
        }

        for(int i=count; i<v;i++){
            if(depth>=1){
                if(arr[depth-1]<i){
                    arr[depth]=i+1;
                }
            }else arr[depth]=count;
            dfs2(depth+1);
            count++;
        }
    }
}

package backjoon;

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

public class b15651 {
    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());
        graph2 g = new graph2(N,M);
        g.dfs(0);
        System.out.println(g.sb);
    }
}
class graph2{
    int v;
    int m;
    int[] arr;
    int depth=0;

    StringBuilder sb;
    public graph2(int v, int m){
        this.v = v;
        this.m = m;
        arr = new int[m];
        sb = new StringBuilder();
    }
    public void dfs(int depth){
        if(depth==m){
            for(int i : arr){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=0; i<v; i++){
            arr[depth]=i+1;
            dfs(depth+1);
        }
    }
}

package backjoon;

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

public class b15652 {
    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());
        graph3 g = new graph3(N,M);
        g.dfs(0,0);
        System.out.println(g.sb);
    }
}
class graph3{
    int v;
    int m;
    int[] arr;
    boolean[] visit;
    StringBuilder sb = new StringBuilder();
    public graph3(int v,int m){
        this.v = v;
        this.m = m;
        arr = new int[m];
        visit = new boolean[v];
    }
    public void dfs(int at, int depth){
        if(depth==m){
            for(int i : arr){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=at; i<v; i++){
            arr[depth]=i+1;
            dfs(at,depth+1);
            at++;
        }
    }
}