패스트캠퍼스 챌린지 9일차

날짜 : 2021 년 11 월 9 일
시청 강의 : 01. 어떻게든 푼다. 완전 탐색 (Brute Force)

완전탐색

모든 경우를 전부 탐색

4가지 문제 유형으로 나누어 볼 수 있음.

[문제유형]
1. N개의 원소 중 중복 없이  M 개를 순서있게 나열
2. N개의 원소 중 중복 없이  M 개를 고르기
3. N개의 원소 중 중복 허용하여 M 개를 순서있게 나열
4. N개의 원소 중 중복 허용하여 M 개를 고르기

완전탐색으로 문제를 풀 때, 백트래킹이 자주 사용되는데 dfs는 백트래킹 문제 방법 중 하나임

따라서, 완전탐색으로 문제를 풀이하는 경우에,

public static void recurrsive(int depth){
	//재귀
}

public static void main(String[] args){
	recurrsive(0);
}

위의 형태가 자주 쓰인다.

나는 완탐은 보통 순열, 조합, 부분집합을 많이 사용하는데 dfs를 활용하면 런타임 에러가 좀 덜 날것같아서 앞으로 되도록 dfs를 사용하고자 한다.

 

앞서 제시한 4가지 문제 유형을 아래 문제들로 연습해 볼 수 있다.

N과 M (3)	https://www.acmicpc.net/problem/15651
N과 M (1)	https://www.acmicpc.net/problem/15649
N과 M (4)	https://www.acmicpc.net/problem/15652
N과 M (2)	https://www.acmicpc.net/problem/15650

 

N 과 M (1)

중복 없이 M 개를 고르는 수열: 이미 고른 원소는 고를 수 없음

수열은 사전 순으로 출력함

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author June Park
 * @date 11/09/2021
 * N과 M (1) 문제 : N 개 중 M 개를 중복 없이 뽑음
 * */
public class BOJ_15649_N과M1 {
	static int N,M ,num[];
	static boolean visited[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); //N개 중
		M = Integer.parseInt(st.nextToken()); //M개를 뽑는다
		num = new int [M];				  	  //방문한 번호를 넣을 배열
		visited = new boolean[N+1];			  //방문처리
		dfs(0);
	}
	
	
	private static void dfs(int depth) {
		if(depth == M) {					 //M개를 뽑음
			for(int i =0 ; i < M ; i++) {
				System.out.print(num[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i = 1 ; i <= N ;i ++) {
			//조건
			if(visited[i]) continue;
				visited[i] = true; //방문처리
				num[depth] = i;//현재 
				dfs(depth+1);//재귀
				visited[i] = false;//release
			
		}
		
	}

}

 

N과 M(2)

package com.fastcamp.backtracking;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
 * @author June Park
 * @date 11/09/2021
 * 중복 없이 M 개를 고름
 * 오름차순
 * */
public class BOJ_15650_N과M2 {
	static int N,M ,num[];
	static boolean visited[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); //N개 중
		M = Integer.parseInt(st.nextToken()); //M개를 뽑는다
		num = new int [M];				  	  //방문한 번호를 넣을 배열
		visited = new boolean[N+1];			  //방문처리
		dfs(0);
	}
	private static void dfs(int depth) {
		if(depth == M) {
			for(int i:num)System.out.print(i+" ");
			System.out.println();
			return;
		}
		
		for(int i = 1; i<= N ;i ++) {
			if(visited[i]) continue;
			if(depth>0 && num[depth-1]>i)continue;
			//Else:
			visited[i] = true;
			num[depth] = i;
			dfs(depth+1);
			visited[i] = false;
		}
		
	}
	

}

N과 M(3)

package com.fastcamp.backtracking;

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

/**
 * @author June Park
 * @date 11/09/2021
 * N과 M (3) : 중복 허용
 * */
public class BOJ_15651_N과M3 {
	static int N,M ,num[];
	static BufferedWriter bw;
	//static boolean visited[];
	public static void main(String[] args) throws Exception {
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); //N개 중
		M = Integer.parseInt(st.nextToken()); //M개를 뽑는다
		num = new int [M];				  	  //방문한 번호를 넣을 배열
		//visited = new boolean[N+1];			  //방문처리
		br.close();
		dfs(0);
		bw.flush();
		bw.close();
	}
	private static void dfs(int depth) throws IOException {
		if(depth == M ) {
			for(int i : num)bw.write(i+" ");// System.out.print(i+" "); 
			bw.write("\n");
			return;
		}
		for(int i = 1 ;i <=N ;i ++) {
			//visited 필요 없음
			num[depth] = i;
			dfs(depth+1);
		}
		
	}
	
}

 

위 3번 문제는 bufferedWriter를 쓰지 않으면 시간 초과 에러가 난다.

따라서, bw에 write 한 후에 main에서 한번에 flush하고 닫아주면 시간초과 에러를 해결할 수 있다.

N과 M(4)

package com.fastcamp.backtracking;

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

/**
 * @author June Park
 * @date 11/09/2021
 * N과 M (4) : 중복 허용
 * 비내림차순 : 중복은 허용(2 2 가능)되나 2 1 은 불가
 * */
public class BOJ_15652_N과M4 {
	static int N,M ,num[];
	static BufferedWriter bw;
	//static boolean visited[];
	public static void main(String[] args) throws Exception {
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); //N개 중
		M = Integer.parseInt(st.nextToken()); //M개를 뽑는다
		num = new int [M];				  	  //방문한 번호를 넣을 배열
		//visited = new boolean[N+1];			  //방문처리
		br.close();
		dfs(0);
		bw.flush();
		bw.close();
	}
	private static void dfs(int depth) throws IOException {
		if(depth == M) {
			for(int i : num)bw.write(i+" ");
			bw.write("\n");
			return;
		}
		for(int i = 1 ; i<= N ;i ++) {
			//방문조건 필요없음
			if(depth!=0 && num[depth-1]>i)continue; //이전 원소가 지금보다크면 skip
			num[depth]= i;
			dfs(depth+1);
			
		}
		
	}
}

 

 

이번 문제들을 풀면서 dfs 를 좀 더 잘 이해하게 된 것 같다.

 

---

패스트캠퍼스 환급 챌린지 바로가기👉 https://bit.ly/3FVdhDa

수강료 100% 환급 챌린지 | 패스트캠퍼스

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.