[백준 알고리즘 자바] 15649 : N과 M (1)

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

15649번: N과 M (1)

---

문제

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력

• 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

• 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
• 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
• 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

입출력 예제

---

풀이방식

이번 문제는 DFS 중에서도 백트래킹에 대한 문제이다.

• 백트래킹 : 어떤 노드의 유망성을 판단한 뒤, 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식 노드를 찾는 알고리즘이다.

---

설계과정

1. 방문여부를 저장할 배열(ch)과 출력할 값을 저장할 배열(graph)을 선언한다.

2. 입력받은 값에서 구할 수 있는 수열을 1부터 N까지 찾는다.

3. 찾은 값이 중복되지 않았다면 방문했다는 의미로 ch 배열에 1을 넣는다.

4. 그 후에 graph 배열에 찾은 값을 넣어준다.

5. 이 때, graph 배열의 인덱스는 맨 처음 입력받은 값으로 지정한다.

6. 재귀함수를 호출하여 과정을 반복한다. 단, 이 때 재귀함수는 +1을 해서 호출해야한다.

• 해당 레벨에 대해서 모든 결과를 찾은 후에, 다음 레벨로 가기 위해서이다.

7. 재귀함수를 호출한 후에는 이전에 방문했던 값들에 방문하지 않았다는 의미로 0을 넣어준다.

• 그래야 다음 레벨에서 다시 탐색할 수 있다. (레벨은 아래 이미지를 참고하자.)

8. 결과값을 출력한다.

---

풀이과정

1. 전역으로 변수를 선언하고 main에 코드를 작성한다.

• 값 입력받고, 함수 호출하고, 결과를 출력하는 코드이다.
• ch[ ] : 방문 여부를 확인할 값이 들어있는 배열이다.
• graph[ ] : 연결 정보를 저장한다.

2. 바로 DFS() 메소드 구현으로 넘어가보자.

 

3. v 와 M 이 동일하면 graph 배열에서 값들을 꺼내 출력한다.

• v 와 M 이 동일하다는 것은 M개의 수를 다 골랐으니 출력한다는 의미이다.
• StringBuilder를 사용했으므로 줄바꿈 문자열을 추가해준다.

4. 동일하지 않고, 방문하지 않았으면 해당 수를 방문했다고 값을 변경하고, graph[] 배열에 값을 넣는다.

• ch[] 값이 0이면 방문을 하지 않은 것이고, 1이면 방문을 한 것이다.
• 여기서 방문이란 해당 수를 이미 골랐다는 의미이다.
• 예제를 기준으로 해서 맨 처음 단계라면 graph[0] = 1 이 들어간다.
• for문을 통해 해당 과정을 반복하게 되면 graph[0] = 1 2 3 4 가 된다.

5. 재귀함수를 호출하되, 1을 더해서 다음 값을 호출한다.

• 1을 더함으로써 다음 레벨에 값을 넣을 수 있게 한다.
• 예제를 기준으로 하면 graph[0] = 1 2 3 4 가 저장된 후에, graph[1] 이 되어 다음 수열을 찾는 것이다.

6. 방문 한 노드에서 되돌아가면서 해당 노드를 방문하지 않은 값으로 다시 바꿔준다.

---

답안소스

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

public class Main {
	static int N, M;
	static int[] ch;
	static int[] graph;
	static StringBuilder sb = new StringBuilder();
	
	public void DFS(int v) {
		if(v == M) {
			for(int x : graph) {
				sb.append(x).append(" ");
			}
			sb.append("\n");
			return;
		} else {
			for(int i=1; i<=N; i++) {
				if(ch[i] == 0) {
					ch[i] = 1;
					
					graph[v] = i;
					
					DFS(v+1);
					
					ch[i] = 0;
				}
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		Main one = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		graph = new int[M];
		ch = new int[N+1];
		
		one.DFS(0);
		
		System.out.println(sb);
	}
}