15654번

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

15654번: N과 M (5)

이번 문제는 저번 스타트링크 문제를 풀고 백트래킹을 더 공부해야겠다고 생각해서 N과 M을 전부 풀어볼 목적으로 한다.

이 문제는 저번 15649번의 코드를 아주 조금 바꾸면 되기에 간단하게 설명하겠다. 

먼저 각 수열 내부의 중복을 제거해야하지만, 각 수열로 봤을 때 역순은 있어야한다. 그렇기에 방문체크를 사용하여 이 문제를 해결 할 것이다. 출력은 다른 N과 M문제들과 마찬가지로 깊이가 주어진M과 같아지면 출력한다.

 

그래서 주어진 수들을 이용하여 배열을 만들고 그 배열의 값들을 방문하는 방식으로 출력스택이 가득차면 출력하는 방식으로 한다.

DFS코드는 아래와 같다.

public void dfs(int depth){
    if(depth==m){
        for(int i : answer){
            sb.append(i).append(" ");
        }
        sb.append("\n");
        return;
    }
    for(int i=0; i<v; i++){
        if(!visit[i]){
            visit[i] = true;
            answer.add(arr[i]);
            dfs(depth+1);
            visit[i]=false;
            answer.pop();
        }
    }return;
}

스택에 값이 쌓일수록 깊이를 증가시켜 깊이가 M이 되면 출력하고, 넣었던 것을 빼는 방식으로 다음 수열에서 재사용가능하게 만든다.

아직 부족한 부분이 많아서 처음에는 방문체크를 사용하지 않고 at변수를 사용하여 시작점을 옮기는 방법으로 해보았는데, 앞에 숫자를 재사용하는 것을 바보처럼 생각하지 못해서 조금 해맸다.

앞에 숫자를 다시 사용하지 않는다면 at을 사용하여 시작지점을 옮겨주는 식으로 중복 없는 출력을 할 수 있다.

 

정답코드는 아래와 같다.

package backjoon.b16654;

import java.io.*;
import java.util.*;
public class b156654 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }//배열 받아오기
        Arrays.sort(arr);//배열을 오름차순으로 출력하기위해
        Graph g = new Graph(N,M,arr);
        g.dfs(0);
        System.out.println(g.sb);
    }
}
class Graph{
    int v;//노드
    int m;//최대 depth
    int[] arr;//입력받은 배열
    boolean[] visit;//방문 판별
    Stack<Integer> answer;//정답출력 스택

    StringBuilder sb;
    public Graph(int v, int m ,int[] arr){
        this.v = v;
        this.arr = arr;
        this.m = m;
        answer = new Stack<>();
        sb = new StringBuilder();
        visit = new boolean[v];
    }
    public void dfs(int depth){
        if(depth==m){
            for(int i : answer){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=0; i<v; i++){
            if(!visit[i]){
                visit[i] = true;
                answer.add(arr[i]);
                dfs(depth+1);
                visit[i]=false;
                answer.pop();
            }
        }return;
    }
}

 

 

 

 

 

 

 

 

 

 

 

이해가 어렵다면 아래의 15649번을 좀 더 봐보면 좋겠다.

https://parkjunbackend.tistory.com/21

b15649번