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

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

15652번: N과 M (4)

 

 

N과 M 시리즈의 마지막 문제를 풀었습니다.

(2) ~ (4)를 순식간에 푼 것 같습니다. 조금 익숙해져서 그런 것 같습니다.

(1) 할 때는 도저히 안풀려서 답을 봤었거든요. 보통 하루에 알고리즘 한문제만 풀려했는데 허허

 

(3)과  비슷합니다. 대신 자신보다 작은 숫자는 다음에 오면 안됩니다. 

 

N과 M 문제 시리즈는 dfs를 사용하는 것 은 똑같지만

크게 3가지로 나뉘는 것 같습니다.

이전값을(prev) 재귀로 넘기느냐 (제가 푼 방식이지만) (이전값과 비교해야할 때 사용)

현재 자릿수로(current) 재귀를 돌리느냐 (이 때 for문 i<=M 주의) -> isVisited 필요없음

다음에 올 숫자로 재귀를(i) 돌리느냐  (이 때 for문 i<M 주의) -> isVisited 필요

 

 

풀이는 다음과 같습니다.

import java.util.Scanner;

public class Main {
    static boolean[] isVisited;
    static int[] num;
    static int n;
    static int m;
    static StringBuilder sb = new StringBuilder();

    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);
        System.out.println(sb);
    }

    static void dfs(int current, int prev) {
        if (current > m) {
            for (int i = 1; i <= m; i++) {
                sb.append(num[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (prev > i) {
                continue;
            }
            num[current] = i;
            dfs(current + 1, i);
        }
    }
}

 

 

 

 

[2020-09-30 복습]

[java]

import java.util.Scanner;

public class Main {
    static boolean[] isVisited;
    static int[] num;
    static int n;
    static int m;
    static StringBuilder sb = new StringBuilder();

    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);
        System.out.println(sb);
    }

    static void dfs(int current, int prev) {
        if (current > m) {
            for (int i = 1; i <= m; i++) {
                sb.append(num[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            if (prev > i) {
                continue;
            }
            num[current] = i;
            dfs(current + 1, i);
        }
    }
}

 

[kotlin]

import java.util.*

internal var isVisited: BooleanArray? = null
internal var num: IntArray? = null
internal var n: Int = 0
internal var m: Int = 0
internal var sb = StringBuilder()

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)
    println(sb)
}

internal fun dfs(current: Int, prev: Int) {
    if (current > m) {
        for (i in 1..m) {
            sb.append(num!![i]).append(" ")
        }
        sb.append("\n")
        return
    }
    for (i in 1..n) {
        if (prev > i) {
            continue
        }
        num!![current] = i
        dfs(current + 1, i)
    }
}

 

 

 

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