[백준] N과 M(1) - 해설

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int M;
    static boolean[] count;
    static StringBuilder sb;
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        sb = new StringBuilder();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N+1];
        count = new boolean[N+1];
        num(0);
        System.out.println(sb);
    }
    public static void num(int index){
        if(index == M){
            for(int i=0; i<M; i++){
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
        }
        for(int i=1; i<N+1; i++){
            if (!count[i]) {
                arr[index] = i;
                count[i] = true;
                num(index+1);
                count[i] = false;
            }
        }
    }
}

 

 

예제 입력 1로 예를 들면 N은 3이고 M은 1이다.

 

    public static void start(int index) {
        //1. start(index)

        if (index == M) { // 8. 
            for (int i = 0; i < M; i++) {
                sb.append(arr[i]).append(" "); // 9. 저장
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i < N + 1; i++) { // 2.
            if (!count[i]) { // 3.
                arr[index] = i; // 4. 
                count[i] = true; // 5.
                start(index + 1); // 6. 
                count[i] = false; // 7. 
            } else { // 10.
            }
        }
    }

9번은 출력라인인데 저장이라고 표현해서 설명

 

1. start(0) 으로 시작

2. 반복문  for(int i=1; i<4; i++)  → 현재 i = 1

4. arr[0] = 1;  → [1, 0, 0, 0]

5. count[1] = true; → [false, true, false, false]

6. start(0+1) 호출

 

1. start(1)

8. index가 1로 M과 같으므로 

9. arr[0]=1 저장

10. count[1] = true이므로 반복문 pass

2. 반복문 for(int i=1; i<4; i++) → 현재 i = 2;

4. arr[1] = 2; → [1, 2, 0, 0]

5. count[2] = true; → [false, true, true, false]

6. start(1+1) 호출

1. start(2) 

10. count[1] & count[2] = true이므로 반복문 pass

2. 반복문 for(int i=1; i<4; i++) → 현재 i = 3;

4. arr[2] = 3; → [1, 2, 3, 0]

5. count[3] = true; → [false, true, true, true]

6. start(2+1) 호출

 

1. start(3)

10. count[1], count[2], count[3] = true이므로 반복문 pass

2. start(2)의 i=3에서 마지막 코드인 7번을 실행

7. count[3] = false → [false, true, true, false]

 

1. start(1)

2. start(1)에서 i = 2의 마지막 코드인 7번 실행

7. count[2] = false → [false, true, false, false]

2. 반복문은 1~3까지이므로 → 현재 i = 3

4. arr[1] = 3; → [1, 3, 3, 0]

5. count[3] = true; → [false, true, false, true]

 

.

.

.

 

이런 흐름으로 진행됨