[Java] N과 M 1 [15649번]

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

• 예제 입력1

3 1

• 예제 출력1

1
2
3

• 예제 입력2

4 2

• 예제 출력2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

• 예제 입력3

4 4

• 예제 출력3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

---

• 문제 접근
  • 대표적인 백트래킹의 DFS 문제
  • boolean 배열을 이용하여 모든 경우의 수를 탐색
• 문제 해결
  • 1 ~ N개의 수에서 길이가 M인 수열을 공백으로 출력
  •  
  • visited[N] 배열을 이용하여 방문 여부를 확인

• 기존 풀이  [메모리 : 22664KB / 시간 : 284ms]

static StringBuilder sb = new StringBuilder();
static int N, M;
static int[] arr;
static boolean[] visited; // 방문 확인 배열
public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] input = br.readLine().split(" ");
    N = Integer.parseInt(input[0]);
    M = Integer.parseInt(input[1]);
    visited = new boolean[N];
    sequence = new int[M];
    DFS(0);
    System.out.println(sb);
}

private static void DFS(int depth) {
    if(depth == M) { // 깊이와 길이가 같아졌다 => 배열이 꽉 찼다
        // 배열 출력
        for(int num : sequence){
            sb.append(num).append(" ");
        }
        sb.append("\n");
        return;
    }

    for(int i = 0; i < visited.length; i++){
        if(!visited[i]){ // 방문한 곳이 아니라면
            visited[i] = true; // 방문한 것으로 체크
            sequence[depth] = i + 1; // 현재 깊이의 방 번호에 값 추가
            DFS(depth + 1); // 깊이를 1 늘려 재귀 호출
            visited[i] = false; // 재귀가 끝나면 i번 방의 방문을 false로 변경
        }
    }
}

• Stream 풀이  [메모리 : 43452KB / 시간 : 460ms]

static StringBuilder sb = new StringBuilder();
static int numCount, length;
static boolean[] visited;
static int[] arr;
public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] input = Arrays.stream((br.readLine().split(" "))).mapToInt(Integer::parseInt).toArray();
    numCount = input[0]; length = input[1];
    visited = new boolean[numCount]; // 방문 여부를 확인할 배열
    arr = new int[length]; // 꽉 차면 출력할 배열
    DFS(0);
    System.out.println(sb);
}

private static void DFS(int depth){
    // 깊이와 길이가 같아졌다 => 배열이 꽉 찼다
    if(depth == length){
        Arrays.stream(arr).forEach(num -> sb.append(num).append(" "));
        sb.append("\n");
        return;
    }

    IntStream.range(0, numCount) // 0 ~ numCount - 1까지 반복
            .filter(i -> !visited[i]) // 방문하지 않았다면 실행
            .forEach(i -> {
                visited[i] = true; // 방문한 것으로 체크
                arr[depth] = i + 1; // 현재 깊이의 방 번호에 값 추가
                DFS(depth + 1); // 깊이를 1 늘려 재귀 호출
                visited[i] = false; // 재귀가 끝나면 i번 방의 방문을 false로 변경
            });
}

 

---

일반 반복문 [메모리 : 22664KB / 시간 : 284ms] vs 스트림 API [메모리 : 43452 KB / 시간 :460ms]

ChatGPT에 의하면 재귀 호출에 스트림을 사용 시 아래와 같은 이유들로 성능의 저하가 발생할 수 있다고 함

1. 추가적인 오브젝트 생성 : 스트림은 람다 표현식과 내부 반복자를 사용하여 처리하므로 일반적인 반복문보다 더 많은 객체가 생성되고 관리
2. 추가적인 메서드 호출 : 스트림 API는 메서드 체이닝을 통해 작업을 수행하므로, 추가적인 메서드 호출이 발생 → 성능에 영향
3. 최적화 부족 : 백트랙킹과 같은 특정 패턴은 전통적인 반복문을 통해 최적화가 가능한 반면, 스트림 API는 이러한 최적화를 잘 활용하지 못할 수 있음