문제 출처

https://www.acmicpc.net/problem/15649
단계별로 풀어보기 > 백트래킹 > N과 M (1)

문제 설명

접근 방법

숫자 조합을 만들기 위해 DFS를 이용한다.

dfs 함수를 만들어 반복문을 통해 각 자리(depth)의 숫자를 순차적으로 지정하고 해당 숫자를 사용 여부 visited 배열에서 true로 바꾼 뒤, dfs를 depth+1의 dfs를 진행한다.

이 후, visited[i] = false로 변경하여 다른 조합에도 대비한다.

import java.util.*;


public class N과_M_1 {

    static int arr[];
    static boolean visited[];

    // dfs 접근
    public static void dfs(int depth, int m){
        if(depth == m){
            for(int k : arr){
                System.out.print(k + " ");
            }
            System.out.println();
            return;
        }
        // 반복문을 통해 조합 변경
        for(int i = 1; i<visited.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            arr[depth] = i;
            dfs(depth+1, m);
            visited[i] = false;
        }

    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int m = scanner.nextInt();

        visited = new boolean[N+1];
        arr = new int[m];

        dfs(0, m);

    }
}

Review

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

public class BOJ_15649_N과_M_1_review {

    static int permute[];
    static boolean visited[];

    public static void dfs(int depth, int length){
        if(depth == length){
            for(int k : permute){
                System.out.print(k + " ");
            }
            System.out.println();
            return;
        }

        for(int i = 1; i<visited.length; i++){
            if(visited[i]) continue;
            visited[i] = true;
            permute[depth] =i;
            dfs(depth+1,length);
            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());

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

        visited = new boolean[N+1];
        permute = new int[M];

        dfs(0,M);

        br.close();
    }
}

알게된 점

처음 문제를 풀이할 때, 출력을 String st에 계속 더하여 조합이 완료된(depth == m)인 경우 출력하려 했으나, 이 방법은 맨 앞에 " "(공백) 이 생긴다는 단 점이 있어서 숫자조합을 기록하는 배열을 생성하는 방법으로 바꿨다.

import java.util.*;


public class Main {

    static boolean visited[];

    // dfs 접근
    public static void dfs(String st, int depth, int m){
        if(depth == m){
            System.out.println(st);
            return;
        }
        // 반복문을 통해 조합에 맨 앞에 오는 경우 변경
        for(int i = 1; i<visited.length; i++){
            visited[i] = true;
            String result = st + " " +i;
            dfs(result,depth+1, m);
            visited[i] = false;
        }

    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        int m = scanner.nextInt();

        visited = new boolean[N+1];

        dfs("", 0, m);

    }
}

문제푼 흔적

Review