[JAVA] 백준 (실버3) 15649번 N과 M (1)

링크

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

---

문제 설명

(정답률 62.707%)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

---

입력 예제

4 2

---

출력 예제

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

---

정답 코드

DFS(깊이우선탐색)을 사용한다.
방문할 노드를 체크하기 위해 boolean 배열과
값을 담을 int 배열을 static으로 생성한다.

dfs 메서드에서
반복을 진행하는데
해당 노드를 방문하지 않았더라면
배열에 값을 할당하고
depth를 1씩 증가시켜 재귀를 호출한다.
깊이가 M과 같아지면 배열을 호출하고 return

위 예제를 예로 들어보겠다.

• dfs(0)
  • i = 1
    • visit = { true, false, false, false }
    • arr[0] = i = 1
    • dfs(1)
      • i = 1 (이미 방문했으니 pass)
      • i = 2
        • visit = { true, true, false, false }
        • arr[1] = 2
        • dfs(2), arr = {1, 2} 출력
        • visit = { true, false, false, false }
      • i = 3
        • visit = { true, false, true, false }
        • arr[1] = 3
        • dfs(2), arr = {1, 3} 출력
        • visit = { true, false, false, false }
      • i = 4
        • visit = { true, false, false, true }
        • arr[1] = 4
        • dfs(2), arr = {1, 4} 출력
        • visit = { true, false, false, false }
    • visit = { false, false, false, false }
  • i = 2
    • visit = { false, true, false, false }
    • arr[0] = 2
    • dfs(1)
      • i = 1
        • visit = { true, true, false, false }
        • arr[1] = 1
        • dfs(2), arr = {2, 1} 출력
          ...

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N;
    static int M;
    static int[] arr;
    static boolean[] visit;
	static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();   	//1 ~ n 자연수
        M = sc.nextInt();  		//m개 선택
        int depth = 0;			//재귀 깊이 판단
        
        arr = new int[M];		//출력할 수열
        visit = new boolean[N + 1];	//방문 여부
        dfs(depth);
        System.out.println(sb);
    }
	//dfs 메서드
    static void dfs(int depth) {
		//깊이가 M이면 배열값을 sb에 추가한 뒤 return
        if (depth == M) {
            for (int val : arr) {
                sb.append(val).append(" ");
            }
            sb.append("\n");
            return;
        }
		//N만큼 반복
        for (int i = 1; i <= N; i++) {
        	//반문하지 않은 노드라면
            if (!visit[i]) {
                visit[i] = true;	//방문으로 변경
                arr[depth] = i;		//배열에 값을 할당
                dfs(depth + 1);		//depth를 1증가시켜 재귀 호출
                visit[i] = false;	//재귀 호출이 끝나면 다시 미방문 상태로 변경
            }
        }
    }
}

---

정리

처음 풀어본 백트래킹 문제였다.
이런 알고리즘 문제는 어떻게든 풀어내는 것보다
공부부터 하는게 좋을거 같아서
반대로 풀이를 보고 이해를 하며 학습했다.
처음엔 잘 이해가 가지 않아서
위에 쓴 것처럼 일일이 적어가며 반복되는 값을 확인했다.
N과 M문제는 시리즈가 있던데 최대한 다 풀어보며 익혀야 겠다.