[백준 15650번 : N과 M (2)][JAVA]

풀기 위한 과정

머리로 이해가 잘 안되서 정말 오랜만에 직접 그려보면서 풀었다. 백트래킹은 머리가 꼬이기 시작하면 답이 없는 것 같다. 그림판에 끄적이는 정도로는 완벽한 이해가 안되었다.

가장 고민한 부분

딱히 엄청 어려운 로직은 아니였다.
이미 넣었던 것보다도 더 큰 숫자들만 넣으면 되니까.

그런데 생각보다 그게 컨트롤이 안되었다. 왜냐하면 depth를 통해 조건을 만들고 싶은데 조금 잘못 건드리면 로직 전체가 너무 크게 바뀌어 세밀하게 잘 조정해야했기 때문이다.

처음에는 엄청 무식하게 생각을 했다..

//차례 차례 방문한다.
        for(int i = 0; i < num; i++){
            if(visited[i] == 0){
                if(ary[depth] < i + 1)
            }
        }

그림도 그려보며 내가 어떻게 해야할지 천천히 감을 잡았고

• depth 0인 경우 일단 뭐라도 넣어야하니까 조건을 따지면 안된다.
• 뭐 하나라도 넣고 그 다음에, 이미 넣은 값이 다음에 넣을 값과 비교를 하여 조건을 성립하는 경우에만 넣자

이 2가지를 만족하는 코드를 작성하려하니 정답이 나왔다!

정답률이 어느 정도 있는 것보니 엄청 어려운 건 아닌데..정진하자 부족하다 정말 많이

정답 코드

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

public class Main {
    static int num;
    static int selectNum;
    static int[] ary;
    static int[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        num = Integer.parseInt(st.nextToken());
        selectNum = Integer.parseInt(st.nextToken());
        ary = new int[selectNum];
        visited = new int[num];

        DFS(0);
    }

    private static void DFS(int depth) {//원하는 깊이까지 만들어졌는지 확인해야지
        if(depth == selectNum){
            for(int value : ary)
                System.out.print(value + " ");
            System.out.println();
            return;
        }

        //차례 차례 방문한다.
        for(int i = 0; i < num; i++){
            if(visited[i] == 0){
                if(depth != 0 && ary[depth-1] > i+1)//이미 들어가있는 수가 더 크다! => 건너뛰자
                    continue;
                ary[depth] = i+1;//ary에 넣자
                visited[i] = 1;//방문표시하자
                DFS(depth+1);
                //방문 완료면 되돌려놓자!
                visited[i] = 0;
            }
        }
    }
}