[Baekjoon] 15649 - N과 M (1)

📝 문제

 

 

🔑 풀이 과정

· DFS 방식을 사용했다. 이전에 프로그래머스에서 타겟 넘버라는 문제를 풀었을 때, 현재 depth를 인자로 넘겨서 탐색 깊이를 제한하는 방식을 학습했었다. 여기서 이 방식을 사용했다. 이래서 문제를 많이 풀어봐야 ㅎㅎ...

그 문제 풀이는 여기 ↓

https://seohyun0916.tistory.com/203

[Programmers] 타겟 넘버

 

· 한 위치에서 끝까지 탐색 한 후, 다시 나와서(트리기준으로 올라가서) 다음 인덱스로 탐색을 또 해야 하므로 방문 배열을 true로 했다가 다시 false로 풀어줘야 한다는 것 (예를들어 2 3 1 4순으로 탐색한 후, 1의 위치(세번째 자리)로 가서 4를 다시 탐색해서 2341을 만들어야 함), 깊이를 인자로 넘겨서 정해진 깊이에 오면 출력해야 한다는 것 까지는 스스로 했는데, 출력하는 부분에서 막혔었다. 그냥 현재의 i를 StringBuilder에 어떻게든 넣어서 출력하려 했다. 그래서 이 부분은 다른분들 풀이를 살짝 참고해서 출력용 배열을 따로 만들면 된다는 것을 알았다.

 

· 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 라는 조건이 있으므로

for문을 i부터 N까지 돌아가게 해준다.

이렇게하면 depth가 0일때 1, 2, 3, 4... depth가 1일때 1, 2, 3, 4... depth가 2일때 1, 2, 3, 4.. 이런식으로 탐색하게 된다.

 

· 손으로 풀어봤던 과정

 

 

🔓 답안

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static StringBuilder sb = new StringBuilder();

    static int N;
    static int M;

    static int[] arr;
    static boolean[] visited;

    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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        //---입력 종료

        arr = new int[M]; //수열을 저장, 출력할 배열
        visited = new boolean[N+1]; //방문 배열

        DFS(0);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    static void DFS(int depth){
        
        if(depth == M){
            for(int num : arr)
                sb.append(num).append(" ");
            sb.append("\n");
            return;
        } else{
            for(int i = 1; i <= N; i++){
                if(!visited[i]){
                    visited[i] = true;
                    arr[depth] = i;
                    DFS(depth + 1);
                    visited[i] = false;
                }
            }
        }
        
    }

}

 

 

 

🖤 알고리즘 분류

- 백트래킹