[백준] 15651번 : N과 M (3) - JAVA [자바]

www.acmicpc.net/problem/15651

15651번: N과 M (3)

 

---

• 문제

 

 

 

 

N과 M (1) 문제와 매우 비슷하다. 아니 오히려 쉽게 풀 수 있다. N과 M (1) 과 달라진 점이라면 중복여부를 고려하지 않아도 된다는 점이다.

 

 

 

 

 

 

 

 

---

• 알고리즘 [접근 방법]

 

사실 이 문제는 어렵지 않다. (어쩌면 이 문제가 N과 M (1) 이여야 하는게 더 맞지 않을까...)

 

1 부터 N까지 M의 길이로 조합할 수 있는 조합을 오름차순으로 나열만 하면 되는 문제기에 사실 매우 간단하게 짤 수 있다. 그래도 백트래킹의 기본기를 위해 다시 설명해보고자 한다. 일단, 백트래킹 카테고리의 문제로 처음 이 문제를 접했다면 아래 포스팅을 한 번 읽고 오는 것을 추천드린다.

 

st-lab.tistory.com/114#알고리즘

[백준] 15649번 : N과 M (1) - JAVA [자바]

 

 

위 포스팅을 보고 왔다는 가정하에(또는 이미 이해하고 있다는 가정하에) 이 번에는 이러한 백트래킹 문제를 DFS 를 사용하여 풀려고 할 경우 어떻게 쉽게 짤 수 있을지에 대해 같이 연계하여 알고리즘을 풀어보고자 한다.

 

 

 

 

 

1. 조건을 보자

 

이러한 백트래킹 문제의 경우 가장 먼저 해야할 것은 문제의 '조건'을 확인하는 것이다. 위 문제에서의 조건은 크게 3가지로 나타낼 수 있다.

  1) 1 ~ N 까지의 수를 조합한다.

  2) M 개를 선택하여 조합한다. (길이(깊이)가 M이다)

  3) 중복해서 조합 할 수 있다.

 

이를 토대로 조건을 구성해야겠다.

 

 

 

2. 재귀함수를 만들자

 

백트래킹의 경우 대표적으로 DFS(깊이우선탐색)으로 구현할 수 있다. DFS의 경우 깊이 우선 탐색이므로, 1부터 중복이 가능한 조합으로 4개를 뽑는다고 가정하면 가장 첫 번째로 탐색하게 될 루트는 1-1-1-1 일 것이다. 그 다음 1-1-1-2 일테고, 이런식으로 가장 마지막(가장 깊은) 노드까지 들어가 가장 깊은 노드부터 탐색하고 더이상 탐색할 자식 노드가 없으면 부모노드로 돌아가(백트래킹) 다음 자식노드를 탐색하는 것이 바로 DFS 다.

 

즉, 다음과 같이 탐색과정을 코드를 짤 수 있다.

void DFS(int depth) {
	/*
	 깊이가 최대 깊이일경우
	 더이상 탐색할 자식노드는 없으므로 return해준다.
	*/
	if(depth == M) {
		return;
	}
    
	/*
	 깊이를 1씩 증가시키면서 DFS를
	 재귀호출한다.
	*/
	for(int i = 1; i <= N; i++) {
		// 만약 추가 조건이 있다면 반복문 안에 추가하면 된다.
		DFS(depth + 1);
	}
}

 

 

이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다. (사실 위 참고 링크를 보고 오셨다면 아마 금방 풀으셨을 것이다.)

 

 

 

 

 

 

 

 

---

• 2가지 방법을 사용하여 풀이한다.

 

이전 포스팅과 여타 다를 바 없이 아래와 같이 3가지 입출력 방법을 통해 성능을 비교해보려 했으나, 역시나 Scanner 와 System.out.print 로 반복출력을 하게되면 '시간 초과'가 뜬다.

그러니 이번에는 출력은 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.

 

1 . Scanner + StringBuilder

2. BufferedReader + StringBuilder

 

 

 

 

---

• 풀이

- 방법 1 : [Scanner + StringBuilder]

 

import java.util.Scanner;

public class Main {
	
	public static int[] arr;
	public static int N, M;
	public static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		N = in.nextInt();
		M = in.nextInt();

		arr = new int[M];
        
		dfs(0);
		System.out.print(sb);

	}

	public static void dfs(int depth) {
		// 깊이가 M이랑 같아지면 출력후 return
		if (depth == M) {
			for (int i = 0; i < M; i++) {
				sb.append(arr[i] + " ");
			}
			sb.append('\n');
			return;
		}

		for (int i = 1; i <= N; i++) {
			arr[depth] = i;
			dfs(depth + 1);
		}
	}

}

 

 

가장 기본적인 방법이라 할 수 있겠다.

 

앞서 말했듯 StringBuilder 가 아니라 System.out.print(arr[i] + " "); 로 하게되면 시간초과가 나므로 주의하자.

StringBuilder 대신 BufferedWriter를 써도 된다.

 

 

---

- 방법 2 : [BufferedReader + StringBuilder]

 

 

 

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.

 

 

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

public class Main {
	
	public static int[] arr;
	public static int N, M;
	public 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());

		arr = new int[M];
		dfs(0);
		System.out.println(sb);
	}

	public static void dfs(int depth) {

		if (depth == M) {
			for (int i = 0; i < M; i++) {
				sb.append(arr[i]).append(' ');
			}
			sb.append('\n');
			return;
		}

		for (int i = 1; i <= N; i++) {
			arr[depth] = i;
			dfs(depth + 1);
		}
	}

}

 

 

 

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

채점 번호 : 20597227  -  방법 2 : BufferedReader + StringBuilder

채점 번호 : 20597227  -  방법 1 : Scanner + StringBuilder

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

---

• 정리

 

이 번 문제 또한 어려운 점은 없었을 것이다. 백트래킹의 대표적 문제는 Queen문제가 아닐까 싶은데, 지금 이 백트래킹 문제들을 확실하게 익히는 것을 추천한다. 생각보다 엄청 많이 쓰이는 해결 방법 중 하나가 백트래킹이기 때문에.. 만약 어렵거나 이해가 되지 않은 부분이 있다면 언제든 댓글 남겨주시면 최대한 빠르게 답변드리겠다.