[알고리즘] 백준 15650 N과 M (2) -백트랙킹- 자바 코틀린

 

 

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

15650번: N과 M (2)

 

 

저번에 N과 M (1) 백트랙킹에 이어서 그 다음단계의 백트랙킹 문제를 풀어보았습니다.

저번 문제와 차이점은 오름차순으로 안된 수는 출력하면 안되는 조건이 붙었습니다. (저번 문제는 모든 경우의 수를 오름차순으로 출력시키는 문제였습니다.)

 

함수에 이전 값을 전달해서 현재숫자와 비교를 하는 로직을 추가했습니다

 

저번 문제를 이해하고 푸니 이번에는 쉽게 풀린 것 같습니다.

 

import java.util.Scanner;

class Main {
    static int N;
    static int M;
    static boolean[] isVisited;
    static int[] num;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        isVisited = new boolean[N + 1];
        num = new int[N + 1];

        dfs(0, -1);
    }

    static void dfs(int current, int prevNum) {
        if (current == M) {
            for (int i = 0; i < M; i++) {
                System.out.print(num[i] + " ");
            }
            System.out.println();
        } else {
            for (int i = 1; i <= N; i++) {
                if (isVisited[i] == true) {
                    continue;
                }
                // 이전 값과 비교
                if (prevNum > i) {
                    continue;
                }
                isVisited[i] = true;
                num[current] = i;
                dfs(current + 1, num[current]);
                isVisited[i] = false;
            }
        }
    }
}

 

 

 

 

 

 

 

 

[2020-09-30 복습]

 

[java]

import java.util.Scanner;

public class Main {
    static boolean[] isVisited;
    static int[] num;
    static int n;
    static int m;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        isVisited = new boolean[m + 1];
        num = new int[m + 1];
        dfs(1, -1);
    }

    static void dfs(int current, int prevNum) {
        if (current > m) {
            for (int i = 1; i <= m; i++) {
                System.out.print(num[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (isVisited[current]) {
                continue;
            }
            if (prevNum >= i) {
                continue;
            }
            isVisited[current] = true;
            num[current] = i;
            prevNum = i;
            dfs(current + 1, prevNum);
            isVisited[current] = false;
        }
    }
}

 

 

[kotlin]

import java.util.*

internal var isVisited: BooleanArray? = null
internal var num: IntArray? = null
internal var n: Int = 0
internal var m: Int = 0

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    n = sc.nextInt()
    m = sc.nextInt()
    isVisited = BooleanArray(m + 1)
    num = IntArray(m + 1)
    dfs(1, -1)
}

internal fun dfs(current: Int, prevNum: Int) {
    var prevNum = prevNum
    if (current > m) {
        for (i in 1..m) {
            print(num!![i].toString() + " ")
        }
        println()
        return
    }
    for (i in 1..n) {
        if (isVisited!![current]) {
            continue
        }
        if (prevNum >= i) {
            continue
        }
        isVisited!![current] = true
        num?.set(current, i)
        prevNum = i
        dfs(current + 1, prevNum)
        isVisited!![current] = false
    }
}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !