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

 

문제

 

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

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

 

 

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

15649번: N과 M (1)

 

이 문제는 백트래킹의 기초문제입니다.

BFS, DFS는 잘 모른다면 구글에 "백트래킹 알고리즘" or "BFS 알고리즘" 을 검색하여 아 이런거구나 정도이해를 하고 오시면 될 것 같습니다. 

 

 

 

 

 

입, 출력

 

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

 

출력은 한줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

 

// 입력1
4 2

// 출력1
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

// 입력 2
4 4

// 출력 2
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

 

 

 

 

 

풀이 (설명)

 

Tip) 풀이 코드는 아래에 있습니다.

 

입력 값인 4 3 을 입력했을 때의 출력 시각화

손수 만들라고 보니 엉망이지만, 그래도 중복 안되고 오름 차순으로 된 수열 값을 시각화 해보았습니다. 

 

녹색 = depth1, 파란색  = depth2, 빨간색 = depth3인 것을 알 수 있습니다.

이에따라 왼쪽부터 아래로 보면 (1, 2, 3) (1, 2, 4) (1, 3, 2) ... (4, 3, 2)이런식으로 나오는 것을 확인 할 수 있습니다.

 

\

 

예시 흐름 설명

1. depth1에 있는 것들을 반복문 돌릴건데 하나의 값 마다 재귀 호출
   예시) 녹색2 → 파랑3 → 빨강4, 녹색3 → 파랑1 → 빨강2
2. 현재의 깊이에 있는 숫자를 int[] 에 넣는다.
   예시) int[] {2, 3, 4} , int[] {3, 1, ?}  : 아직 depth2까지 밖에 호출 안했을 때
3. 내가 원하는 깊이 까지 재귀 호출한다.
4. 하나의 값이 있는지 체크하기 위해 boolean[] 에 저장한다.
   예시) depth1 에 1이 와서 int[] 에 1이 존재하면 boolean[1] 은 true가 되어 존재 한다는 것을 알리는 구조
5. 호출이 완료 됐으면 boolean[1]은 false로 원래대로 돌린다.

 

즉, 4개의 숫자(1, 2, 3, 4)를 가지고 3개를 조합하여 중복안되는 숫자를 만들고 오름차순으로 만들겠다라는 문제입니다.

 

 

이 문제의 포인트

• 재귀 호출로 인한 깊이 탐색
• 값을 배열로 값을 넣어 중복 제거

 

 

 

 

 

풀이 (코드)

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int[] iArr;  // 출력할 배열
    static boolean[] visit; // 값 중복 여부
    static StringBuilder sb = new StringBuilder();

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

        StringTokenizer stn = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(stn.nextToken());
        int M = Integer.parseInt(stn.nextToken());
        iArr = new int[M];  // 출력할 배열
        visit = new boolean[N+1];   // 값 중복 여부, 1 부터 N까지 이므로 N+1

        dfs(N, M, 0);
        System.out.println(sb.toString());
    }

    public static void dfs(int N, int M, int depth){
        if(depth == M){ // 내가 원하는 깊이면 중지
            for(int i : iArr){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = 1; i <= N; i++){
            if(!visit[i]) { // 값이 존재하지 않는다면
                visit[i] = true;
                iArr[depth] = i;
                dfs(N, M, depth + 1);
                visit[i] = false;   // 다 끝나면 원래 대로
            }
            
        }
    }

}

 

 

 

 

 

 

추가

 

boolean[]을 통해서 중복을 체크했었는데 이것이 생각이 안날 경우

int[] 에 있는 값과 현재 depth에서 반복문 돌릴 때의 값을 비교한 적이있었다.

성능은 안좋지만 그래도 이렇게도 풀 수 있었다는 것을 보여주고 싶다.

 

코드 보기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    static int[] iArr;
    static boolean[] visit;

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

        StringTokenizer stn = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(stn.nextToken());  // 이루어진 숫자
        int M = Integer.parseInt(stn.nextToken());  // 깊이
        iArr = new int[M];
        visit = new boolean[M];

        dfs(N, M, 0);
    }

    public static void dfs(int N, int M, int depth){
        if(depth == M){ // 내가 원하는 깊이면 중지
            for(int i : iArr){
                System.out.print(i+ " ");
            }
            System.out.println();
            return;
        }

        // 더 들어 가야 한다면 재귀
        for(int i = 0; i < N; i++){
            if(!includeCheck(i+1, depth)) {
                iArr[depth] = i + 1;
                dfs(N, M, depth + 1);
            }
        }
    }

    public static boolean includeCheck(int num, int depth){
        for (int i = 0; i < depth; i++) {
            if (iArr[i] == num)  return true;
        }

        return false;
    }
}

 

 

 

 

감사합니다.