[백준] 10974번 모든 순열 JAVA (자바) 풀이

문제 10974번 (백트래킹)

 

 :  1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성

 

 

 [입력]

 :  첫째 줄에 N(1 ≤ N ≤ 8)

 [출력]

 :   첫째 줄부터 N개의 줄에 걸쳐서 모든 순열을 사전순으로 출력

 

 

 [과정]

 

 탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 

 

 문제 조건 1) 숫자 중복금지 
 문제 조건 2) 수열 원소 오름차순 

 

 종료 조건) 배열이 M만큼 채워지면 출력하고 boolean false

 

 N과 M(1) 문제와 비슷하다
 방문기록을 체크해가며 숫자를 추가한다

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,arr[];
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        visit = new boolean[N];
        
        back(0);
    }
    
    public static void back(int depth){
        if(depth==N){
            for(int i:arr){
                System.out.print(i+" ");
            }
            System.out.println();
            return;
        }
        
        for(int i = 0; i<N;i++){
            if(!visit[i]){
                visit[i]=true;
                arr[depth]=i+1;
                back(depth+1);
                visit[i]=false;
            }
        }
    }
}

 

 

 [해설]
     

 :  static int arr[],N;
    static boolean visit[];
    
 :  N = Integer.parseInt(br.readLine());  첫번째줄 입력
    arr = new int[N];  출력할 배열
    visit = new boolean[N];  방문기록
        
  :  back(0);  백트래킹 시작
    
  :  public static void back(int depth){
        if(depth==N){  종료조건
            for(int i:arr){  arr 배열 출력
                System.out.print(i+" ");  StringBuilder 대신에 print로 이어서 출력
            }
        System.out.println();  다음 배열부터 개행
        return;
        }
        
        for(int i = 0; i<N;i++){  N번 for문 돌기
            if(!visit[i]){  방문기록 없을 경우
                visit[i]=true;  방문 체크
                arr[depth]=i+1;  해당 깊이에 i+1 넣기
                back(depth+1);  다음 깊이 백트래킹 반복
                visit[i]=false;  방문 초기화
            }
        }
    }
  

 

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

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

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *