[백준 15649] Java - N과 M (1)

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

 

 

N과 M (1)

 

 

1)  문제

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

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

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

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

 

 

2)  예시

예제입력 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

3)  풀이

 

* 아이디어
1) 중복 없이 골라야 하므로 방문 체크 배열 필요 (boolean[] visited)

2) 순서를 고려하므로 순열

3) 백트래킹 구조

 

 

 

 

4)  코드

import java.util.Scanner;
// 자바 유틸의 Scanner를 이용하기위해, 사용자로부터 N, M값을 입력받게


public class Main {
// 메인클래스 정의

    static int N, M;
	// N : 1부터 N까지의 숫자범위, M : N개중 M개를 골라 출력할 개수
    // 클래스 내에서 사용가능하도록 static으로 정의
    static int[] result;
	// 정수배열 result 정의
    static boolean[] visited;
	// visited[i]: 숫자 i가 현재 순열에 이미 사용되었는지 여부를 체크하는 배열
	// 중복없이 선택해야하므로 필요함



    public static void dfs(int depth) {
	// 깊이우선탐색을 재귀로 표현한 메소드 정의, depth : 현재까지 선택한 숫자의 개수
        if (depth == M) {
	// 종료조건으로 M개를 모두 선택했으면 종료합니다.
            for (int i = 0; i < M; i++) {
                System.out.print(result[i] + " ");
	// result[] 배열에 저장된 숫자들을 출력
	// 각 숫자 뒤에 공백을 붙여 출력하고, 줄바꿈으로 한줄씩 출력
            }
            System.out.println();
            return;
        }


        for (int i = 1; i <= N; i++) {
	// 1부터 N까지 시도하는 반복문
            if (!visited[i]) {
	// 숫자 i가 선택되지 않았다면
                visited[i] = true;
	// i를 선택했다고 바꾸고
                result[depth] = i;
	// 현재 depth 위치에 i를 기록합니다.
	// 예를 들어 depth = 0이면 첫번째 숫자를 선택하는 중
                dfs(depth + 1);
	// 다음 숫자를 선택하기위해 재귀호출(자기 자신의 함수)
                visited[i] = false; // 백트래킹
	// 재귀가 끝나고 돌아오면 숫자 i를 다시 사용 가능하게 합니다.
	// 이 부분이 백트래킹의 핵심 (다음 경우의 수를 위해 이전 상태로 되돌리기)
            }
        }
    }


    public static void main(String[] args) {
	// 자바 프로그램의 시작점
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();  // 숫자의 범위
        M = sc.nextInt();  // 뽑는 개수

        result = new int[M];
	// 길이가 M인 배열 생성 -> 결과값 저장
        visited = new boolean[N + 1];
	// 인덱스를 1부터 쓰기위해 N+1 크기의 boolean 배열 생성
        dfs(0);
	// 깊이 0부터 탐색시작 -> 순열의 시작
    }
}

 

 

 

// 예시의 DFS 탐색흐름

dfs(0)                           // depth = 0
 └── i = 1 선택 → visited[1] = true → result[0] = 1
     └── dfs(1)                 // depth = 1
         └── i = 1 → skip (이미 선택됨)
         └── i = 2 선택 → visited[2] = true → result[1] = 2
             └── dfs(2)         // depth = 2
                 ✔ 출력: 1 2
             ← visited[2] = false (백트래킹)
         └── i = 3 선택 → result[1] = 3 → 출력: 1 3
         └── i = 4 선택 → result[1] = 4 → 출력: 1 4
     ← visited[1] = false (백트래킹)

 └── i = 2 선택 → result[0] = 2
     └── dfs(1)
         └── i = 1 선택 → result[1] = 1 → 출력: 2 1
         └── i = 3 선택 → result[1] = 3 → 출력: 2 3
         └── i = 4 선택 → result[1] = 4 → 출력: 2 4
     ← visited[2] = false

 └── i = 3 선택 → result[0] = 3
     └── dfs(1)
         └── i = 1 선택 → 출력: 3 1
         └── i = 2 선택 → 출력: 3 2
         └── i = 4 선택 → 출력: 3 4
     ← visited[3] = false

 └── i = 4 선택 → result[0] = 4
     └── dfs(1)
         └── i = 1 선택 → 출력: 4 1
         └── i = 2 선택 → 출력: 4 2
         └── i = 3 선택 → 출력: 4 3
     ← visited[4] = false

 

 

 

 

 

5)  리뷰

처음에는 dfs(depth) 함수가 도대체 뭘 하는지 감이 안 왔는데,
재귀적으로 숫자를 하나씩 선택하고, depth == M일 때 출력하는 구조라는 걸 이해하고 나니
전체 흐름이 눈에 들어오기 시작했다.

특히 visited[] 배열을 사용해서 중복을 방지하고,
재귀가 끝난 후 다시 visited[i] = false로 돌려주는 백트래킹 부분이 핵심이라는 것도 알게 됐다.
단순한 순열이지만, 재귀와 백트래킹의 기본을 익히기에 딱 좋은 입문 문제였다고 생각한다.