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

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

---

[접근 방법]

참 간단해 보이는 문제인데, 손도 못대겠어서 상당히 당황하였다.

 

DFS를 그래프 탐색 알고리즘으로만 알고 있어서, 이러한 문제에도 활용할 수 있는지 몰랐다.

 

DFS를 이용한 다른 사람의 풀이를 참고하였다.

 

먼저, DFS에 필요한 변수들이 있다.

방문 여부를 판단할 boolean "visit 배열",

M개의 숫자의 수열을 저장할 int "arr 배열",

문제에서 입력으로 주어지는 N, M 과 그래프의 깊이를 나타내는 depth 변수이다.

 

static int[] arr; // M개의 숫자로 이루어진 수열 저장
static boolean[] visit; // 방문여부를 기록.
static StringBuilder sb; // 출력을 위함.

public static void dfs(int N, int M, int depth){

	// arr에 M개의 숫자가 채워서 수열이 완성되면 출력
    if(depth == M) {
    	for(int val : arr){
        	sb.append(val).append(" ");
        }
        sb.append("\n");
        return;
    }
    
    // 0 ~ N-1 의 범위
    for(int i=0; i<N; i++){
    	
        // 방문한적이 없는 경우
        if (!visit[i]) {
        	visit[i] = true;
            arr[depth] = i + 1; // index : depth 에 저장
            dfs(N, M, depth + 1); // 깊이 증가 후 재귀호출
            visit[i] = false; // 복원
        }
    }
    return;
}

---

[JAVA 코드]

// 15649번 - N과 M (1)
import java.util.*;
import java.io.*;

public class Main {

    static int[] arr;
    static boolean[] visit;
    static StringBuilder sb;

    public static void dfs(int N, int M, int depth){
        
        // 수열에 M개의 숫자가 채워지면 출력
        if (depth == M){
            for(int val : arr){
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }

        // 0 ~ N-1 범위
        for(int i=0; i<N; i++){

            if (!visit[i]) {

                visit[i] = true;
                arr[depth] = i + 1; // arr[0], arr[1], ... 순서대로 M개 저장
                dfs(N, M, depth + 1);

                visit[i] = false;
            }
        }
        return;
    }

    public static void main(String[] args) throws IOException {
       
        // 0. 입출력 선언 / 초기화
        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]; // 길이 M인 수열 저장 공간
        visit = new boolean[N]; // 방문여부 확인
        sb = new StringBuilder();

        dfs(N, M, 0);
        
        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 브루트포스 문제를 푸는데 DFS를 모르니 풀기 어려웠음.

 

2. 알게된 점

- for(int val : arr){ ... } 로 배열 원소들을 출력하는 방법이 멋있다고 생각함.

- DFS에 대해 어렴풋이 알게됨.

 

3. 개선 방향

- 반복학습만이 답이라고 생각함.