백준알고리즘: p15649~15652 N과 M(1, 2, 3, 4)

분류: 백트래킹

 

처음에 백트래킹도 생소하고 어떻게 접근해야될 지 몰라서 다른 사람들이 어떻게 풀었는지 설명을 좀 찾아봤다. 

st-lab.tistory.com/114?category=862595 이 글에서 많이 도움을 받았다. 

나중에 잘 모르겠으면 다시 보기... 백트래킹 설명과 dfs와의 차이점 등을 알 수 있었다. 

 

▶문제15649

 

 

▶코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package backtracking;

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

public class p15649 {
//1부터 N까지의 수로 M개 짜리 수열 모두 출력해라
	public static int[] arr;
	public static boolean[] visit;
	public static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int N = Integer.parseInt(s[0]);
		int M = Integer.parseInt(s[1]);
		
		arr = new int[M];//출력될 수열들
		visit = new boolean[N];//인덱스(+1)숫자의 방문여부
		
		dfs(N, M, 0);
		System.out.print(sb);
	}
	
	public static void dfs(int N, int M, int depth) {
		
		if(depth == M) {
			for(int val : arr) {
				sb.append(val+" ");
			}sb.append("\n");
			return;
		}
		
		for(int i=0; i<N; i++) {
			if(visit[i]==false) {
				visit[i] = true;
				arr[depth] = i+1;
				
				dfs(N, M, depth+1);
				visit[i] = false; //방문하고 나왔으면 다시 false로 바꿔줘야 다른 얘가 방문할 때 들어갈 수 있다.				
			}
		}
		
	}

}

▶재귀호출시 ++대신 +1하기

++ 은 depth 변수의 값 자체가 1 증가하기 때문에 재귀에서 빠져나와도 증가된 값은 그대로 유지되기 떄문

 

▶arr베열은 출력될 수열이 들어갈 배열이고, visit은 1~N까지의 숫자 중 중복을 거르기 위해 arr배열에 넣어도 되는지 확인하는 용도의 boolean 배열이다.

depth는 깊인데, M과 같아지면 리턴하는 메소드를 위해 있어야 한다. (깊이우선탐색,,)

 

 

▶채점결과

---

▶문제 15650

▶코드

package backtracking;

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

//1~N까지 오름차순인 M개의 수열을 출력해라.
public class p15650 {
	public static int N;
	public static int M;
	public static int[] arr;
	public static boolean[] visit;
	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];
		visit = new boolean[N];
		
		dfs(0, 0);
		System.out.print(sb);

	}
	
	public static void dfs(int start, int depth) {
		if(depth==M) {
			for(int val : arr) {
				sb.append(val+" ");
			}sb.append("\n");
		return;
		}
		
		for(int i=start; i<N; i++) {//i를 0이 아니라 start부터 돌도록
			if( visit[i]==false) {
				visit[i] = true;
				arr[depth] = i+1;
				dfs(i+1,depth+1);//start를 현재 노드의 값+1해줘서 오름차순인 수열만 만들어지도록 
				visit[i] = false;
			}
		}
	}

}

▶result

 

---

▶문제15651

▶코드

package backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//수열 중복은 안되지만, 수열 내 중복은 허용.
public class p15651 {
	public static int N;
	public static int M;
	public static int[] arr;
	public static boolean[] visit;
	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];
		visit = new boolean[N];
		
		dfs(0);
		System.out.print(sb);

	}
	
	public static void dfs(int depth) {
		if(depth==M) {
			for(int val : arr) {
				sb.append(val+" ");
			}sb.append("\n");
		return;
		}
		
		for(int i=0; i<N; i++) {
				visit[i] = true;
				arr[depth] = i+1;
				dfs(depth+1);
				visit[i] = false;
		}
	}
}

▶채점결과 

---

▶문제15652

▶코드

package backtracking;

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

public class p15652 {
//비내림차순 11 12 13 22 23 33
	public static int N;
	public static int M;
	public static int[] arr;
	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, 0);
		System.out.print(sb);

	}
	
	public static void dfs(int start, int depth) {
		if(depth==M) {
			for(int val : arr) {
				sb.append(val+" ");
			}sb.append("\n");
			return;
		}
		
		for(int i=start; i<N; i++) {//중복허용하지만 같거나 크도록 (비내림차순)
				arr[depth]=i+1;
				dfs(i, depth+1);
		}
		
	}

}

▶채점결과

---

네 문제가 거의 비슷하지만 조금씩 다르게 구현하면 되는 문제였다.

백트래킹에 대해서도 알면서 좋은 공부가 된것 같다. 

첫 문제는 블로그에서 보고 시작했지만 다음 문제부턴 내가 풀 수 있었다. 

다음에도 이런 문제가 있으면 알아서 해결할 수 있도록 하고싶다.