[백준] 15650번 : N과 M (2) - JAVA [자바]

www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

---

• 문제

 

 

 

저번 백트래킹 N과 M (1) 에 이은 매우 간단한 문제다!

 

 

---

• 알고리즘 [접근 방법]

 

 

이 문제 또한 그리 어렵지 않다!

 

만약 백트래킹 문제로 이 문제를 처음 접하신다면 먼저 아래 글을 꼭 참고하시길 바란다.

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

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

 

 

기본적으로 이러한 부류의 백트래킹문제는 dfs 탐색방식을 사용한다.

 

다만 이 문제의 특징이라하면 N과 M을 입력받으면 "1부터 N까지의 수 중 오름차순이면서 M의 길이까지 나열 가능한 수열"이어야 한다. 위 문제에서 예제 입력 3을 보면 알 수 있듯이 4 4 를 입력받으면 1 2 3 4 만 만족한다.

 

그럼 어떻게 재귀함수를 만들 수 있을까??

 

일단 기본 포멧은 이렇다.

public static void rec(int at, int depth) {
		
	if(depth == M) {
		/*
		 깊이가 M이랑 같을경우 출력
		*/
	}
	
	/*
	 재귀하면서 백트래킹 할
	 반복문 구현
	*/
	for(/*...*/) {
		// 반복문 내용
	}
	
}

 

 

이번에는 이전과는 다르게 깊이를 의미하는 depth 변수뿐만 아니라 at 변수를 추가해주었다.

at 변수의 의미는 현재 위치, 즉 어디서부터 시작하는지를 의미하는 변수다. 예로들어 반복문에서 재귀를 해 줄 때, at = 1 부터 시작하면 다음 재귀는 오름차순으로 탐색하기 위해 at 을 1 증가시킨 2를 인자로 넘겨주면서 다음 재귀의 반복문이 2부터 시작하도록 하는 변수를 의미한다.

 

즉, 코드로 보면 다음과 같을 것이다.

public static void dfs(int at, int depth) {
		
	if(depth == M) {
		/*
		 깊이가 M이랑 같을경우 출력
		*/
	}
	
	/*
	 i 는 at 부터 탐색하도록 한다.
	*/
	for(int i = at; i <= N; i++) {
		// 현재 깊이를 index로 하여 해당 위치에 i 값을 담는다
		arr[depth] = i;
        
		/*
		 재귀호출 :
		 현재 i 값보다 다음 재귀에서 더 커야하므로
		 i + 1 의 값을 넘겨주고, 깊이 또한 1 증가시켜 재귀호출해준다
		*/
		dfs(i + 1, depth + 1);
	}
	
}

 

 

위와 같이 구성하면 된다.

그러면 현재 arr 배열에 i가 담김과 동시에 다음 재귀에서는 i값보다 1이 큰 수부터 탐색하도록 함과 동시에 depth 또한 1 증가시키면서 재귀호출을 해주면 다음 재귀에서는 at 은 이전 재귀보다 1이 큰 상태가 되고, 반복문에서 결과적으로 이전 값보다 큰 수부터 탐색하게 된다.

 

그리고 이전 문제와 달리 중복방문인지를 고려할 필요가 없으므로 boolean 배열로 중복 여부를 체크할 필요 또한 없다. 차피 재귀 과정에서 만약 모든 배열에 채우지 못하는 경우에는 depth == M 이 될 수 없게되고, 반복문이 먼저 끝나기 때문에 자동으로 걸러지게 된다.

 

그럼 위를 토대로 한 번 여러가지 풀이 방법들을 보도록 하자.

 

 

 

 

 

 

 

 

 

 

---

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

 

알고리즘은 위에서 설명한 알고리즘을 적용할 것이다.

 

다만 성능의 차이를 보기위해 입출력에서 차이를 둘 것인데, 다음과 같은 3가지 방법으로 풀이해보려 한다.

 1. Scanner + System.out.print

 2. Scanner + StringBuilder

 3. BufferedReader + StringBuilder

 

숱하게 입출력에 차이를 두어 풀이해와서 결과야 뻔히 알지만, 혹여 처음 본 분들도 계실테고,, 그러니 양해바란다.

 

 

---

• 풀이

- 방법 1 : [Scanner + System.out.print]

 

import java.util.Scanner;

public class Main {

	public static int[] arr;
	public static int N, M;

	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

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

		arr = new int[M];
        
		dfs(1, 0);

	}

	public static void dfs(int at, int depth) {

		if (depth == M) {
			for (int val : arr) {
				System.out.print(val + " ");
			}
			System.out.println();
			return;
		}
        
		for (int i = at; i <= N; i++) {

			arr[depth] = i;
			dfs(i + 1, depth + 1);

		}
	}
}

 

 

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

 

오히려 이전 문제보다 코드가 간결하다. 그리고 다시한번 언급하지만, 위 코드에서 재귀호출 시 i++, depth++ 을 해주면 반드시 재귀호출 다음 라인에 i--, depth-- 또한 써야한다. 아니면 자체 i 값이 증가하기 때문에 재귀호출에서 빠져나올 때도 증가 된 값 그대로 남아있게 된다.

 

 

 

 

---

- 방법 2 : [Scanner + StringBuilder]

 

 

 

출력방법을 달리하여 푸는 방법이다. 아무래도 입력 개수보다 출력할 것이 더 많기 때문에 이러한 문제에서 더욱 큰 효율을 볼 수 있다. 특히 StringBuilder 자체가 문자열을 하나로 묶어줄 수 있는 역할을 하기 때문에 더욱 속도가 빠르기도 하다.

단 StringBuilder을 main 함수와 dfs 함수에서 모두 접근해야하므로 정적타입으로 선언해준다.

 

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(1, 0);
		System.out.print(sb);

	}

	public static void dfs(int at, int depth) {

		if (depth == M) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
        
		for (int i = at; i <= N; i++) {

			arr[depth] = i;
			dfs(i + 1, depth + 1);

		}
	}
}

 

 

 

 

---

- 방법 3 : BufferedReader + StringBuilder 

 

 

 

 

입력을 Scanner 대신 BufferedReader 로 사용한 방법이다.

필자의 카테고리 중 Java에 입력관련 포스팅을 보면 알겠지만, BufferedReader 가 성능이 좋다는 건 두 말하면 잔소리다. 애초에 Scanner 자체가 정규식 검사 과정에서 꽤 많은 시간을 소비하기 때문에...

 

그리고 문자열 분리는 StringTokenizer 를 사용했다. 

 

 

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

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(1, 0);
		System.out.println(sb);

	}

	public static void dfs(int at, int depth) {

		if (depth == M) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
        
		for (int i = at; i <= N; i++) {

			arr[depth] = i;
			dfs(i + 1, depth + 1);

		}
	}
}

 

 

 

 

매우 쉽지 않은가?? 필자 느낌으로는 오히려 이전 문제(N과 M (1))보다 쉽게 느껴지긴 한다만.. 

 

 

 

 

 

 

 

 

---

• 성능

 

 

위에서 부터 순서대로

 

채점 번호 : 20545644  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 20545640  -  방법 2 : Scanner + StringBuilder

채점 번호 : 20545636  -  방법 1 : Scanner + System.out.print

 

 

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

출력의 경우는,, 가끔 출력 할 케이스가 1개일 때가 있어서 그런가.. 큰 차이까진 아니고 약간의 차이는 볼 수 있는 것 같다.

 

 

 

 

---

• 정리

 

백트래킹의 두 번째 문제였다.

 

이 문제는 상대적으로 고려할 것이 적어 더욱 쉽게 풀지 않았을까 생각이 든다. 혹여 이해가 안된다거나, 자신이 짠 코드가 잘 되지 않는다면 언제든 질문 드리면 빠르게 답변드리겠다.