[백준] N과 M(1) 15649번 (PYTHON,JAVA)

✔ 문제 15649 N과 M(1)

문제 바로가기 💨 

15649번: N과 M (1)

핵심 아이디어

백트래킹을 사용하여 N개의 자연수 중에서 M개를 고르는 모든 경우의 수를 출력해야 한다. 백트래킹은 가능한 모든 해를 탐색하는 알고리즘 중 하나로, DFS(깊이 우선 탐색)를 기반으로 한다.

dfs 함수는 현재 선택한 숫자의 개수를 나타내는 n과 현재까지 선택된 숫자들의 리스트 lst를 인자로 받는다.
종료조건을 먼저보자. n이 M과 같아지면, 즉, M개의 숫자조합을 모두 선택했을 때는 lst를 정답 리스트인 ans에 추가하고 함수를 종료한다.
종료 조건에 해당하지 않는 경우, 현재 선택된 숫자의 개수가 M보다 작으므로 다음 숫자를 선택한다.
1부터 N까지의 숫자를 반복하면서, 아직 선택되지 않은 숫자인 경우(중복 제외)에만 선택하고, 그 숫자를 리스트 lst에 추가한 뒤 dfs 함수를 재귀적으로 호출한다.
재귀 호출이 끝나면(다음 노드 탐색이 끝나면), 방문했던 숫자를 해제한다.

이후 모든 경우의 수를 찾으면 정답 리스트 ans를 출력한다.

 

이때, 방문,다음노드 dfs후 방문 해제를 하는 이유는 다음 순회에서 이전에 선택한 숫자를 다시 선택할 수 있도록 하기 위함이다.

내가 헷갈렸던 부분은 dfs를 재귀호출하고 방문해제를 하는부분인데, dfs는 스택 recursion 구조이므로 끝 단까지 간 후, 마지막 노드이면 방문해제를한다.그럼 다음 이전 노드로 이동해 또 방문해제...하는 식으로 이루어지는 것이다..!

 

---

PYTHON

def dfs(n, lst):
    # 종료조건(n에 관련...n은 노드 개수) 처리+정답처리
    if n==M:
        ans.append(lst)
        return
    
    # 하부단계(함수)로 호출 ((현재 기준으로 생각...))
    for j in range(1, N + 1):
        if v[j] == 0: # 선택하지 않은숫자인 경우 추가
            v[j] = 1
            dfs(n + 1, lst+[j])
            v[j] = 0

N, M = map(int, input().split())
ans = [] # 정답 리스트를 저장할 리스트
v = [0] * (N + 1) # 경로중복확인을 위한 visited[]

dfs(0, [])
for lst in ans:
    print(*lst)

JAVA

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int n, m;
    static boolean[] visit;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        visit = new boolean[n + 1];
        arr = new int[m]; // 한 path 경로 (하나의 조합) 담을 배열
        dfs(0);
        System.out.println(sb);
    }
    
    private static void dfs(int depth) { //헷갈리면depth를 현재까지의노드개수 n이라 생각하면 편함!
        if(depth == m){
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }
        
        for(int i = 1; i <= n; i++){ // 노드들 탐색
            if(!visit[i]) { // 아직 노드 방문하지않았다면
                visit[i] = true; // 탐색 노드 방문상태 변경
                arr[depth] = i; 
                dfs(depth + 1); // 다음 탐색
                visit[i] = false;
            }
        }
    }
}