[백준] N과 M (1)-Java
in Algorithm on Algorithm
[백준] 15649-N과 M (1)-Java
❓문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
🖊️풀이법
이번 문제는 백트리킹 카테고리의 첫번째 문제이다.
백트래킹이란 해석하면, ‘되추적’이라는 말로, 알고리즘적으로 설명 하나의 결과를 찾는 도중 결과가 아닌 값을 마주했을 때 돌아가서 다시 결과를 찾는 것을 말한다.
DFS(깊이우선탐색)
이번 문제의 경우 백트래킹의 대표적인 방법 중 하나인 DFS(깊이우선탐색)를 이용하여, 풀 수 있다.
DFS란 깊이 우선 탐색법으로, 위의 사진과 같이 상위노드에서 가장 깊은 노드까지 탐색한 후 탐색하지 않은 노드를 깊이 순서대로 순차적으로, 탐색하는 방법을 말한다.
예를들어 1 - 2 - 3 - 4 까지 깊이우선으로 탐색 후 다시 1부터 1 - 2 - 3 - 5로 탐색하는 것이 아니라 상위 노드에 분기되어진 다른 하위노드를 탐색했는지를 판별하고, 탐색하지 않았다면 탐색 후 다시 상위노드로 돌아가는 형식의 탐색방법이다.
Point
- depth로 노드의 깊이를 변수로 설정한다.
- boolean[] visit로 해당 노드를 탐색했는지 하지 않았는지 여부를 확인한다.
- 위의 두가지 설정으로 모든 노드를 탐색하고 출력한다.
정답 코드
import java.util.*;
import java.io.*;
public class Main {
static int[] arr;
static boolean[] visit;
static StringBuilder sb = new StringBuilder();
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());
arr = new int[M]; // 정답을 담을 배열 생성
visit = new boolean[N]; //탐색했는지 여부를 확인하는 배열생성
dfs(N, M, 0); //dfs매서드 실행
System.out.println(sb); //정답 출력
}
public static void dfs(int N, int M, int depth){
if(depth == M){ //만약 depth가 M과 같으면, 최대깊이를 순회했기 떄문에
for(int i : arr){ //arr에 담은 정답 출력
sb.append(i).append(' ');
}
sb.append('\n');
return;
}
for(int i = 0; i < N; i++){ //N번만큼 반복
if(!visit[i]){ //만약 visit[i]가 false이면 아직 순회하지 않은 노드이므로
visit[i] = true; //상태를 true로 변경 후
arr[depth] = i + 1; //해당 arr[depth]에 값 할당
dfs(N, M, depth + 1); //다음 depth의 노드 탐색을 위해 depth값을 +1후 dfs 재귀호출
visit[i] = false; //하나의 상위노드를 모두 탐색했다면, 다음 노드 dfs를 위해, 상태변경
}
}
}
}
정리
오늘 첫 백트래킹 문제였는데, 재귀호출과 함께 엮여있어서, 꽤나(?) 애를 많이먹었고 다른 사람의 코드를 많이 참조하고 공부한 시간이 된것 같아서 한편으로 뿌듯하다
언젠가.. 내 스스로 이 모든 것들을 구현할 수 있게 되길 희망한다 :)