🔺 문제
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] A; // 현재까지 선택한 숫자 저장 배열
static boolean[] visited; // 방문 상태 배열
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(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[M]; // 배열에 M개의 선택된 숫자 저장
visited = new boolean[N];
dfs(0);
System.out.println(sb);
}
public static void dfs(int depth) {
if(depth == M) { // 재귀 종료 조건
for(int val : A) {
sb.append(val).append(" ");
}
sb.append("\n");
return;
}
for(int i = 0 ; i < N ; i++) {
if(!visited[i]) {
visited[i] = true;
A[depth] = i + 1; // 선택된 숫자 저장
dfs(depth + 1); // 다음 자식 노드 방문을 위해 depth를 1 증가시키고 재귀호출
visited[i] = false; // 자식 노드 방문 끝나고 돌아오면, 방문노드 상태를 방문하지 않은 상태로 변경
}
}
}
}
|
cs |
✅ 해결 아이디어
✔ 백트래킹
- DFS 수행하며, 노드의 유망성을 판단해 가지치기하고, 다시 부모 노드로 돌아가 다른 자식 노드 탐색
💥 유의사항
• depth++로 해주면 답이 달라지므로, depth + 1을 해준다.
(만약 depth++를 사용하고 싶다면, dfs 재귀 호출 다음 줄에 depth-- 를 해줘야한다.)
🔺 다른 풀이들
- 과정 설명 최고...
[백준] 15649번 N과 M(1) - Java, 자바
실버 3 https://www.acmicpc.net/problem/15649N과 M 시리즈는 백트래킹 시리즈이다.이제 이것을 하나하나 풀어가보려고 한다. 백트래킹이란 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면
velog.io
- 와 친절한 과정 설명 최고,,, (백트래킹 전체 복습용 풀이로도 좋은 글 같다,,,)
[백준알고리즘-JAVA]15649번 풀이(N과M2) - 초보도 이해하는 풀이
안녕하세요 인포돈 입니다. 백준 알고리즘 15649번 풀이입니다. * 참고사항 - 개발환경은 eclipse을 기준으로 작성되었습니다. - java언어를 이용하여 문제를 풀이합니다. - 알고리즘 문제는 풀이를
infodon.tistory.com
💬 느낀 점
DFS는 백트래킹의 일부,,,
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V | 8.24 |
(+ 2회독 8.24)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] A; // 현재까지 선택한 숫자 저장 배열
static boolean[] visited; // 방문 상태 배열
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(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
A = new int[M];
visited = new boolean[N];
dfs(0);
System.out.println(sb);
}
private static void dfs(int depth) {
if(depth == M) {
for(int val : A) {
sb.append(val).append(" ");
}
sb.append("\n");
return;
}
for(int i = 0 ; i < N ; i++) {
if(!visited[i]) {
A[depth] = i + 1; // 선택된 숫자 저장 (갱신)
visited[i] = true;
dfs(depth + 1);
visited[i] = false;
}
}
}
}
|
cs |
(참고)
✔ 무한한 감사를 드리는...
[백준] 15649번 : N과 M (1) - JAVA [자바]
www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열
st-lab.tistory.com
[ 백준 15649 / Java ] N과 M(1)
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
codesign.tistory.com
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 15651번: N과 M (3) (1) | 2023.06.05 |
---|---|
[백준/JAVA] 15650번: N과 M (2) (0) | 2023.06.05 |
[백준/JAVA] 1874번: 스택 수열 (0) | 2023.06.04 |
[백준/JAVA] 9251번: LCS (0) | 2023.06.04 |
[백준/JAVA] 2565번: 전깃줄 (0) | 2023.06.04 |