250x250
05-19 16:42
관리 메뉴

막내의 막무가내 프로그래밍 & 일상

[알고리즘] 백준 10974 모든 순열 -백트래킹- 자바, 코틀린 본문

알고리즘/DFS, BFS, 시뮬, 백트래킹

[알고리즘] 백준 10974 모든 순열 -백트래킹- 자바, 코틀린

막무가내막내 2022. 1. 4. 21:22
300x250
SMALL

 

 

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

 

10974번: 모든 순열

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

 

오랜만에 백트래킹과 자바 감도 익힐겸 백트래킹 유형에서 기본문제를 풀어봤습니다. ㅎㅎ

요즘 코볼만 쓰고 있는데 자바 정말 오랜만에 쓰네요.... 그립다 자바야 ㅜㅜㅜㅜㅜㅜㅜㅜ

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.Scanner;

public class Main {
    private static int N;

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

    private static void dfs(int depth, boolean[] isVisited, int[] nums) {
        if (depth == N) {
            for (int i = 0; i < nums.length; i++) {
                System.out.print(nums[i] + " ");
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (!isVisited[i]) {
                isVisited[i] = true;
                nums[depth] = i;
                dfs(depth + 1, isVisited, nums);
                isVisited[i] = false;
            }
        }
    }


}

 

[Kotlin]

import java.util.*

private var N = 0
fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    val isVisited = BooleanArray(N + 1)
    dfs(0, isVisited, IntArray(N))
}

private fun dfs(depth: Int, isVisited: BooleanArray, nums: IntArray) {
    if (depth == N) {
        for (i in nums.indices) {
            print(nums[i].toString() + " ")
        }
        println()
        return
    }
    for (i in 1..N) {
        if (!isVisited[i]) {
            isVisited[i] = true
            nums[depth] = i
            dfs(depth + 1, isVisited, nums)
            isVisited[i] = false
        }
    }
}

 

 

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

 

 

 

 

 

300x250
LIST
"이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다."
2 Comments
댓글쓰기 폼