[백준/JAVA] 10974번: 모든 순열

🔺 문제

10974번: 모든 순열

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] A, result;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        for(int i = 0 ; i < N ; i++) {
            A[i] = i + 1;
        }
        result = new int[N];
        visited = new boolean[N];
        
        back(0);
        System.out.println(sb);
    }
    
    private static void back(int depth) {
        if(depth == N) {
            for(int i : result) sb.append(i).append(" ");
            sb.append("\n");
            return;
        }
        
        for(int i = 0 ; i < N ; i++) {
            if(!visited[i]) {    // 중복 제거용
                result[depth] = A[i];
                
                visited[i] = true;
                back(depth + 1);
                visited[i] = false;
            }
        }
    }
}

✅ 해결 아이디어
✔ 백트래킹

 

• Line 33 | if(!visited[i]) 하는 이유 ⇨ 중복 제거용

- 이 처리를 안 하면 숫자 중복이 생긴다. (1 1 1) (1 1 2) (1 1 3) 이런 식으로...

 

---

🔺 다른 풀이들

- 나처럼 result 배열 만들지 않고, A[depth] = i + 1 이런 식으로 값 저장해서 사용하심

[Java] 백준 10974번

---

💬 느낀 점

다른 조건 많은 문제 풀다가 이런 간단한 조건의 문제를 보니까

10분만에 풀었다... 감사합니다...

 

 

1회독	2회독	3회독	4회독	5회독
V