공부 166일차: 백준 10974번 모든 순열 자바 java

10974 모든 순열

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

10974번: 모든 순열

 

 

 

---

백준 10974번 문제 모든 순열

---

문제

---

 

 

 

 

---

과정 생각해보기 & 오답

---

 

https://gimbalja.tistory.com/290

공부 152일차: 백준 15649번 N과 M (1) 자바 java

 

N과 M 문제와 똑같은 요구를 하는 문제다

다만 이번 문제에선 n이 n, m 역할 모두 한다

 

DFS를 구현하되 백트래킹으로 더 이상 시도해보지 않아도 되는 구간은 쳐낸다

 

이 역할을 해주는 것이 boolean 배열이다

(아래 코드가 곧 구현 방식이자 핵심 알고리즘이니 참고)

 

 

 

---

정답 인정 코드

---

 

import java.io.*;
 
public class Main {
    
    static int n;
    static int[] arr;
    static boolean[] visited;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    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];
        visited = new boolean[n];
        
        DFS(0);
        bw.flush();
        bw.close();
    }
    
    static void DFS(int depth) throws IOException{
        if(depth == n) {    // 깊이가 n과 같아지면 == n개의 수가 들어가면
            for(int i : arr) {
                bw.write(i+" ");
            }
            bw.newLine();
            return;
        }
        
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {    // visited[i]가 false 일 때만 수행 -> 중복 수가 걸러진다
                visited[i] = true;
                arr[depth] = i+1;
                DFS(depth+1);
                visited[i] = false;
            }
        }
    }
}
 

 

DFS 기초를 복습하는 단계의 문제라고 보면 될 듯

 

 

 

---