[BOJ - JAVA] 10974 - 모든 순열

# 주소 

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

10974번: 모든 순열

 

# 문제

# 문제 해설 및 코드 리뷰

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	private static int N;
	private static int arr[];
	private static boolean visit[];
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N];
		visit = new boolean[N];
		
		dfs(0);
	}
	
	private static void dfs(int cnt) {
		if(cnt == N) {
			for(int i=0;i<N;i++)
				System.out.print(arr[i]+" ");
			System.out.println();
			return ;
		}
		
		for(int i=0;i<N;i++) {
			if(!visit[i]){
                arr[cnt] = i+1;
                visit[i] = true;
                dfs(cnt+1);
                visit[i] = false;
            }
		}
	}

}

 

이번에도 BufferedReader를 이용하여 풀이를 진행했습니다!

이 블로그 포스팅에서 정말 지겹도록 많이 본 dfs문제입니다. 

입력값이 어느 숫자로 정해져있을 때 1부터 n까지 모든 가지수를 구하는 문제입니다.

 

입력값이 크지 않기 때문에 이 문제는 백트래킹을 이용하여 풀 수 있습니다.

BufferdReader를 이용하여 N을 입력 받고 int형태의 arr과 boolean형태의 visit을 선업합니다. 

이후 dfs(0)을 실행할건데, dfs의 기본 인자는 int형으로 cnt의 값이 0일때 부터 시작합니다.

 

그리고 방문한 요소의 위치와 방문하지 않은 요소의 위치마다 arr[cnt]에 i+1의 값을 넣습니다

(i = 0부터 이므로 자연수를 출력하기 위해)

그리고 재귀함수의 성질을 살려서 dfs(cnt + 1)을 for문 안에 넣고 visit[i]를 false로 바꾸어서 모든 경우의 수를 구할 수

있습니다.