[Java] 백준 15649번 : N과 M (1) <Silver 3>

⚠️ 내맘대로 작성한 코드이기 때문에 비합리적 진행과 근거없는 추론이 있을 수 있습니다!⚠️

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

Code

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
    ArrayList<Integer> result = new ArrayList<>();
    int N;
    int M;

    void run() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] input = bf.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        DFSUtil();
    }

    void DFSUtil(){
        boolean[] visited = new boolean[N];
        for(int i = 0; i < N; i++){
            result.add(i + 1);
            visited[i] = true;
            DFS(visited, 1);
            visited[i] = false;
            result.remove(0);
        }
    }

    void DFS(boolean[] visited, int count){
        if(count < M){
            for(int i = 0; i < N; i++){
                if(!visited[i]) {
                    result.add(i + 1);
                    visited[i] = true;
                    DFS(visited, count + 1);
                    visited[i] = false;
                    result.remove(count);
                }
            }
        }else{
            print();
        }
    }

    void print(){
        for(Integer list:result){
            System.out.print(list + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        Main my = new Main();
        my.run();
    }
}

---

Code 필수 요소

1. 백트래킹 활용

2. 값 관리 방법

 

이것만 생각해내면 절반은 끝났다.

 

// 백트래킹 활용

이번 문제는 백트래킹을 사용했다.

DFS를 통해 자료값을 탐색하는 중 백트래킹을 활용하여 불필요한 정보는 탐색하지 않는 방법을 사용했다.

1차적으로 몇 개를 탐색하는지 확인하는 count, 2차적으로 해당 숫자를 사용했는지 확인하는 visited를 사용했다.

 

// 값 관리 방법

물론 내가 쓴 방법이 정답은 아니지만 난 이렇게 했다.

해당  값을 사용할때 visited를 true로 만들어 해당 숫자를 사용했다는 것을 표시하고, result라는 list에 값을 추가해준다.

이러한 방법으로 값들을 저장해 가다가 마지막 DFS가 끝나게 되면 result에 있는 값을 출력하고 맨뒤의 값을 제거한다. 그 후 해당 값을 visited했다는 것도 제거하여 다음 DFS가 돌아갈때 사용할 수 있도록 했다.

 

// 전체적 설명

DFSUtil에서 첫번째 자릿수를 정해주고, DFS에서 두번째부터 값을 도출하는 방법을 썼다. 그 후 값을 하나씩 방문하며 중복되지 않은 숫자를 하나씩 탐색하는 방법으로 진행했다. 

 

 

생각보다는 어렵지 않았다. 그래도 값을 넣고 DFS를 돌리고 끝난 후 값을 없앤다는 방법을 생각하는데 시간이 조금 걸렸다.

다른사람들 코드 보니까 내꺼보다 훨씬 깔끔하더라. DFSUtil이랑 DFS도 합칠 수 있을거 같은데 못하겠다 어려브

 

-꿑-