[문제 풀이] 백준 15649번 N과 M(1) JAVA _다시풀이

문제

  문제접근 방법   

해당 문제는  N과 M을 입력받고 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 사전 순으로 출력하는 프로그램을 작성하는 문제아다. 해당문제는 DFS + 백트래킹에 대해서 모른다면 접근하기 어려운 문제로 문제를 해결하기 위해서는 해당 알고리즘 개념부터 익히고 오는 것을 추천한다.

문제에 중복 없이 M개를 고르라는 것은 순열을 의미하며 1 ~ N 숫자 중 M개를 순서 있게, 중복 없이 뽑아야 한다.

백트래킹 사용하여  현재 수열에 포함된 숫자를 기록하고, 숫자 하나 추가 → 방문 처리 → 재귀 호출 → 복귀 시 방문 해제(백트래킹)의 흐름으로 진행하려한다. 이후 사전 순 출력을 위해 1 ~ N 순서대로 탐색하고 방문 여부 체크한다. 모든 작업이 끝나면 출력하는 식으로 코드를 작성해보려한다.

 

< 최종 코드 >

import java.util.Scanner;

public class Main {
    static int N, M;
    static boolean[] visited;
    static int[] result;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        N = s.nextInt();
        M = s.nextInt();
        visited = new boolean[N + 1];
        result = new int[M]; 

        dfs(0);
    }

    public static void dfs(int depth) {
        if (depth == M) { 
            for (int num : result) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                visited[i] = true; 
                result[depth] = i;
                dfs(depth + 1);
                visited[i] = false;
            }
        }
    }
}

먼저 전역 변수 선언하는데 선언한 전역변수는 다음과 같다.

 

• N: 1부터 N까지 수 중에서
• M: 수열의 길이
• visited: 중복을 피하기 위해 사용되는 방문 여부 배열
  • visited[i] = true이면 i는 이미 사용됨
• result: 지금까지 만든 수열을 저장하는 배열 (길이 M)

이후 N과 M 입력 받고 visited 를 visited[N+1]로 초기화, dfs(0) 호출해준다.

DFS 함수에서 depth는 현재 수열의 위치를 의미하며 기저 조건은 if (depth == M)로 설정해 현재 수열이 M개가 되면 result 배열을 출력하고 종료하도록 작성하였다. 그리고나서 재귀 탐색 & 백트래킹을 진행하는데 1 ~ N까지 수 중에서 아직 사용하지 않은 숫자 i를 고른다. 조건문 안의 각 코드는 다음과 같은데

 

• visited[i] = true: 해당 숫자를 사용했다고 표시
• result[depth] = i: 현재 자리에 수를 넣음
• dfs(depth + 1): 다음 자리 채우러 감

탐색이 끝난 후에는 visited[i] = false로 되돌린다.

추가 풀이

해당 문제는 dfs와 백트래킹의 기초가 되는 문제라고 생각되어 시간이 지나고 다시 풀어보고 다시풀어보고를 반복했는데

항상 dfs의 기본 틀은 잘 작성되지만 백트래킹에서 시간이 오래 걸렸다. 위에서 처럼 배열로 접근도 가능하지만 

이번에는 처음부터 StringBuilder로 접근하게 되었고 잘 작성했지만 StringBuilder도 백트래킹 처리해야한다는 것을 간과했다.

위에서는  result[depth] = i; 이코드가 값을 넣으면서 해당 깊이에 저장된 값에 덮어쓰는 방식이기 때문에 백트래킹 처리가 자동으로

된것이나 마찬가지인다. 하지만 StringBuilder를 사용하면 값을 넣고 다시 돌리는 과정이 쉽사리 떠오르지 않았다. 

코드는 다음과 같다.

< 최종 코드  ver StringBuilder >

import java.util.*;

public class Main{
    public static boolean visited[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        visited=new boolean[n+1];
        
        StringBuilder sb=new StringBuilder();
        dfs(0,n,m,sb);
    }
    public static void dfs(int depth,int n,int m,StringBuilder sb){
        if(depth==m){
            System.out.println(sb);
            return;
        }
        
        for(int i=1;i<=n;i++){
            if(!visited[i]){
                visited[i]=true;
                int len=sb.length();
                sb.append(i).append(" ");
                dfs(depth+1,n,m,sb);
                sb.setLength(len);
                visited[i]=false;
            }
        }
    }
}

해당 코드처럼 StringBuilder에 저장하기전에 이전 상태 즉, StringBuilder의 길이를 저장하고 재귀가 return되어 백트래킹해주어야할 때, setLength를 통해서 이전에 저장된값을 지우고 길이를 이전 상태로 되돌리는 방식이다.

다음은 BFS로도 구현이 가능하지를 확인해보겠다. 솔직히 최단거리를 구하는 문제가 아니라면 dfs를 사용해야하는지 bfs를 사용해야하는지 헛갈리는 상태이기 때문에 구현해보았다. 

 

< 최종 코드  ver BFS >

 

 

 참고 자료 

• DFS
• 백트래킹