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

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

15649번: N과 M (1)

 

 

 

 

 

백트랙킹 문제를 처음 풀어봤습니다.

풀다가 도저히 안풀려서 백트랙킹 개념과 다른 사람의 풀이를 보았습니다. 백트랙킹 첫번째 문제인데도 저한테는 어렵네요 ㅜㅜ

 

백트랙킹 문제는 dfs 또는 bfs 를 사용할 수 있으며 개념은 다음을 보면 됩니다. 전 dfs를 재귀를 사용하는게 편한 것 같습니다.

https://idea-sketch.tistory.com/29

[알고리즘] 되추적(Backtracking)을 알아보자.

 

 

처음에는 풀이를 보고도 풀이가 잘 이해가 안갔으나 계속보니 이해가 조금씩 되고 다시 풀어보았습니다. 

남의 코드를 보고 이해를 했더니 같은 방식으로 풀어졌습니다. ( 더 좋은 코드를 보며 배우는점도 필요하다고 봅니다. 풀이가 깔끔하더라고요... 이를 토대로 공부를 더 해야겠습니다.)

풀이는 다음과 같습니다.

 

import java.util.Scanner;

public 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(1);

    }

    static void dfs(int current) {
        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[i]) {
                continue;
            }
            isVisited[i] = true;
            num[current] = i;
            dfs(current + 1);
            isVisited[i] = false;
        }
    }


}

제가 이해한대로 설명을 간략하게 하면 다음과 같습니다.

 

 

 

 

 

 

위 백준 입력예시인 4 2 를 예로 들어보겠습니다.

 

1. current는 자리수를 의미합니다. 자리수가 M개가 되었으면 출력을 하게 됩니다. (current는 0부터 시작하고 current+1로 재귀를 돌려서 M개 일때가 두 자리가 num에 채워 진 겁니다.)

2. 각 자리수 num[current]에 값(i)을 넣어주는데 해당 값이 이미 사용한 경우(isVisited[i] 로 판단) 건너뛰고 재귀도 돌려주지 않게 됩니다.

3. 각 자리수를 검사하는데 방문 안한, 즉 사용 안한 값(i)인 경우 방문 처리해주고 현재 자릿수에 해당 값을 넣습니다. (num[current] = i)      그리고 다음 자리수로 재귀를 돌립니다.

4. dfs(current + 1) 은 다음 자리수로 재귀를 돌려줍니다. ( 즉 다음 자리수를 이제 완전탐색 하는 것이지요)

5. 해당 자릿수에 대한 재귀가 끝나면 해당 자릿수에 썻던 값을 다시 방문안한 상태로 되돌려줍니다. ( isVisited[i] = false)

 

그래서 다음과 같이 동작할 것입니다. (틀리면 말씀 좀 부탁드립니다.  빨강은 isVIsited == true 에 걸려서 continue되는 걸 의미하고 파랑은 재귀 후 isVisited 가 다시 false 될 예정을 의미합니다.)

1 => 다음자릿수 재귀

1 1 

1 2 => 다음 자릿수 재귀

1 2 1

1 2 2

1 2 3 => 다음 자릿수 재귀

1 2 3 1

1 2 3 2 

1 2 3 3

1 2 3 4 => 출력

1 2 3 => for문 다시 반복 4할 차례

1 2 4 => 다음 자릿수 재귀

1 2 4 1 

1 2 4 2

1 2 4 3 => 출력

1 2 4 

1 2 => for문 다시 반복 3할 차례

1 3 1

1 3 2

1 3 2 1

1 3 2 2

1 3 2 3

1 3 2 4 => 출력

....

....

....

 

 

 

 

 

[2020-09-26 복습]

import java.util.Scanner;

public 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(1);

    }

    static void dfs(int current) {
        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[i]) {
                continue;
            }
            isVisited[i] = true;
            num[current] = i;
            dfs(current + 1);
            isVisited[i] = false;
        }
    }


}

import java.util.*

internal var N: Int = 0
internal var M: Int = 0
internal var isVisited: BooleanArray? = null
internal var num: IntArray? = null


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    isVisited = BooleanArray(N + 1)
    num = IntArray(N + 1)
    dfs(1)

}

internal fun dfs(current: Int) {
    if (current > M) {
        for (i in 1..M) {
            print(num!![i].toString() + " ")
        }
        println()
        return
    }
    for (i in 1..N) {
        if (isVisited!![i]) {
            continue
        }
        isVisited!![i] = true
        num!![current] = i
        dfs(current + 1)
        isVisited!![i] = false
    }
}