[BaekJoon] 15649번 N과 M (1) 문제 풀이 (Success)

15649번: N과 M (1)

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int[] arr;
    public static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
 
        arr = new int[M];
        visit = new boolean[N];
        dfs(N, M, 0);
        
        br.close();
        
        bw.write(sb.toString());
        
        bw.flush();
        bw.close();
 
    }
 
    public static void dfs(int N, int M, int depth) {
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(' ');
            }
            sb.append('\n');
            return;
        }
 
        for (int i = 0; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                arr[depth] = i + 1;
                dfs(N, M, depth + 1);
                visit[i] = false;
            }
        }
    }
}
 

🤔 해설

1. public static int[] arr;

    - leaf 노드 도착 시, 출력될 배

2. public static boolean[] visit;

    - 중복 제거를 위한 배열

3. arr = new int[M];

    - arr의 크기 = M

4. visit = new boolean[N];

    - 방문 여부 배열의 크기 = N

5. dfs(N, M, 0);

    - root 노드부터 방문 시작

6. if (depth == M) { ... }

    - leaf 노드 도착 시, 출력

7. if (!visit[i]) { ... }

    - 방문하지 않은 노드일 경우,

    - visit[i] = true;

        - 방문 여부를 true로 변경

    - arr[depth] = i + 1;

        - 현재 노드의 위치(=arr 배열에서의 위치)에 1번부터 순차적으로 기재

    - dfs(N, M, depth + 1);

        - 다음 노드의 위치로 이동하여 중복되지 않은 값의 경우, arr 배열에 값 입력

    - visit[i] = false;

        - leaf 노드 도착 시, dfs() 호출이 끝나고 i=0일 때의 1차 순환 마무리

        - i = N-1이 될 때까지 상기 과정 반복

 

 

 

 

🔗 소스 코드
GitHub

 

📚 참고 자료

[알고리즘 PS] 백준 15649번 N과 M (1) 자바 문제풀이