[백준] [15650] N과 M (2) (JAVA) (백트래킹)

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

15650번: N과 M (2)

---

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

68644

51296

36693

74.112%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

※ JAVA 코드 (N과 M (2))

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[] arr;
    static boolean[] visit;

    static ArrayList<Integer> result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // N까지의 숫자를 담을 배열
        arr = new int[N + 1];

        // 방문 체크를 위한 배열
        visit = new boolean[N + 1];

        result = new ArrayList<>();

        // 1~N 까지의 숫자 저장
        for(int i = 1; i <= N; i++) {
            arr[i - 1] = i;
        }

        // 현재 인덱스와 만들어진 배열의 길이를 체크
        solve(0, 0);
    }

    public static void solve(int idx, int cnt) {
        // 만들어진 배열의 길이가 만들고자하는 길이와 같다면 출력
        if(cnt == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(result.get(i) + " ");
            }
            System.out.println();
            return;
        }

        for(int i = idx; i < N; i++) {
            // 방문체크
            if(visit[i] == true) {
                continue;
            }

            visit[i] = true;
            result.add(arr[i]);

            solve(i, cnt + 1);

            visit[i] = false;
            result.remove(result.size() - 1);
        }
    }
}

---

※ 생각정리 (N과 M (2))

 

백트래킹의 접근은 다음 글을 확인해주세요

https://dawn-of-coding.tistory.com/189

[백준] [15649] N과 M (1) (JAVA) (백트래킹)

---

N과 M (2) 문제는 위 문제에서 약간의 변형이 이루어진 문제이다.

1. 기존 전체 수열을 출력 -> 오름차순으로 중복이 없는 수열을 출력

2. 기존에 사용하던 인덱스의 접근 방법을 약간 바꾸어서 재귀를 호출하였다.

for(int i = idx; i < N; i++) {
    // 방문체크
    if(visit[i] == true) {
        continue;
    }

    visit[i] = true;
    result.add(arr[i]);
	
    // 바뀐부분 (idx -> 1)
    solve(i, cnt + 1);

    visit[i] = false;
    result.remove(result.size() - 1);
}

 

N과 M (1)문제는 idx값을 넘겨줌으로서 모든 중복순열을 출력하도록 하였고 N과 M (2)문제는 반복문의 i값을 넘겨줌으로서 오름차순의 순열을 출력하도록 변경해주었다.

 

- 새벽코딩 -