백준 15649 자바 ( N 과 M (1))

<문제>

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

15649번: N과 M (1)

 

<풀이>

1. 어떤 접근으로 문제를 접근하려고 했는지

    일반적인 순열을 출력하는 문제이다.

    visited라는 boolean 배열을 활용해서 사용한 숫자의 경우 해당 인덱스를 True로 바꾼다. true로 되어있을 경우, 재귀함수를 동작하지        않게 코드를 작성한다.

    재귀함수에서 나오게 되면 다시 사용을 해야하기때문에 visited를 False로 다시 바꿔줘서 순열을 구현한다.

 

2. 문제를 해결하기 위한 기능

    숫자를 사용했으면 사용했다고 표시하는 기능

    재귀함수를 통해 순열적으로 동작하는 기능

 

<코드>

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

public class Main {

    public static int n, m;
    public static ArrayList<Integer> arrayList = new ArrayList<>();
    public static boolean[] visited;

    public static void print() {
        for(int i = 0; i < arrayList.size(); i++) {
            System.out.print(arrayList.get(i) + " ");
        }
        System.out.println();
    }
    public static void dfs(int h) {
        if(h == m + 1) {
            print();
            return;
        }
        for(int i = 1; i <= n; i++) {
            if(visited[i]) continue; // 한번 사용한 숫자는 사용안함

            arrayList.add(i);
            visited[i] = true; // 사용했다고 체크
            dfs(h + 1);
            arrayList.remove(arrayList.size() - 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());

        visited = new boolean[n + 1]; // 사용여부 체크 하는 배열

        dfs(1);



    }
}