728x90
난이도 : 실버3
풀이일 : 2401232
https://www.acmicpc.net/problem/15650
링크로 이동하기 귀찮은 분들을 위한 문제 캡쳐
풀이 코드
import java.util.Scanner;
public class Main {
static boolean[] visited; // 중복 방문 방지
static int[] array; // 수열 저장
static int N;
static int M;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
visited = new boolean[N];
array = new int[M];
DFS(0, 0);
}
static void DFS(int depth, int num) {
// 수열이 채워졌으면 순서대로 출력
if (depth == M) {
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
return;
}
// 현재 번호 보다 큰 숫자들만 탐색
for (int i = num; i < N; i++) {
// 이전에 방문하지 않은 노드에 대하여
if (!visited[i]) {
visited[i] = true; // 방문 처리
array[depth] = i + 1; // 수열 현재 깊이 자리에 i + 1 추가
DFS(depth + 1, i); // 재귀 탐색
visited[i] = false; // 자식 노드 탐색 후 방문 처리 초기화
}
}
}
}
- visited : 중복 방문 방지를 위한 방문 여부 확인 배열
- array : 정답 수열을 저장할 배열
- DFS 탐색
- 조건에 해당하는 수열을 오름 차순으로 출력하기 위해, 현재 숫자의 정보를 함께 인자로 받음
- 만약 깊이가 수열의 길이와 같다면, 현재 수열에 있는 숫자들 순서대로 출력
- 현재 숫자 이후의 숫자들에 대한 탐색 과정을 거침
느낀점
- 어제 풀이한 문제에서 오름차순이라는 조건만 추가된 문제였다. 해당 조건을 위해 DFS 함수의 인자를 하나 늘려줬다. 시리즈로 쭉 풀어보면 재미있을 것 같으니까 내일도 N과 M 시리즈 문제를 풀어봐야지.
'알고리즘 > 🥈 실버' 카테고리의 다른 글
백준 15652 N과 M (4) 자바 풀이 (0) | 2024.01.27 |
---|---|
백준 15651 N과 M (3) 자바 풀이 (0) | 2024.01.24 |
백준 15649 N과 M(1) 자바 풀이 (1) | 2024.01.23 |
백준 16953 A -> B 자바 풀이 (0) | 2024.01.21 |
백준 11725 트리의 부모 찾기 자바 풀이 (0) | 2024.01.18 |