문제 출처

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

문제 설명

자연수 N과 M이 주어졌을 때, 1~N까지 중복 없이 M개 고른 수열(오름차순)을 출력하라.

접근 방법

M개의 조합을 가지고 있을 배열 permute에 재귀를 이용하여 조합을 출력한다.
backTracking은 시작(오름차순을 위함), 깊이, N개의 수, M개의 수의 조합을 인자로 받아서
depth == M이면 해당 조합을 출력하고, 아닐 경우 조합을 계속 생성한다.
for에서는 시작 조건을 start로 잡아서 오름차순이 될 수 있도록 설정한다.

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

public class N과_M_2 {

    static int[] permute;
    static boolean[] visited;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void backTracking(int start, int depth, int N, int M) throws IOException{
        if(depth == M){
            StringBuilder sb = new StringBuilder();
            for (int i : permute) {
                sb.append(i).append(" ");
            }
            sb.append("\n");
            bw.write(sb.toString());
            return;

        }
        for(int i = start; i<=N; i++){
            if(visited[i]) continue;
            visited[i] = true;
            permute[depth] = i;
            backTracking(i+1,depth+1,N,M);
            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());

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

        backTracking(1,0,N,M);

        bw.flush();
        bw.close();
        br.close();

    }

}

Review

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

public class N과_M_2_review {

    public static int com[];
    public static boolean visited[];
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void dfs(int depth, int length, int start,int N) throws IOException{
        if(depth == length){
            StringBuilder sb = new StringBuilder();
            for(int i : com){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            bw.write(sb.toString());
            return;
        }

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

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


        dfs(0,M,1,N);

        bw.flush();
        bw.close();
        br.close();
    }

}

알게된 점

처음에 출력할 때, Sort를 하려고 했으나 이를 temp 배열로 permute를 복사하면 기존 permute에 영향을 줘서 안된다는 것을 알았다.

dfs에서 for문을 진행할 때, 다음 dfs 전달하는 인수로 start+1가 아닌 i+1로 전달(이전의 현재 i보다 큰 수가 들어가게 -> 오름차순 적용)

문제푼 흔적

Review