1. 합이 같은 부분집합 (아마존)
문제 풀이
- 합이 홀수 일때 2로 나누면 절대 반이 될수 없음 -> 따라서 NO로 처리
- 합이 짝수 일때 dfs로 부분 집합 나누면 됨
- dfs로 해당 원소 사용한다, 안한다로 풀면 됨
- check 배열은 필요 없음 -> 이유는 dfs 원소의 합을 넣었기 때문에 hap으로 비교하면 됨
- 시간 단축을 위해 ck boolean을 사용 -> ck이면 dfs 더이상 타지 않고 종료 (가지치기)
코드
package inflearn.section8;
import java.util.*;
public class 합이같은부분집합 {
static int total;
static int arr[];
static int n;
static boolean ck;
public static void dfs(int l, int hap) {
if (ck) return; // 시간 단축
if (l==n) {
// 이고 hap이 2로 나누었을때 절반과 같으면 종료
if (hap*2==total) {
ck=true;
}
}
else {
dfs(l+1,hap+arr[l]); // 사용
dfs(l+1,hap); // 안사용
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
arr=new int[n];
total=0;
int max=0;
ck=false;
for (int i=0;i<n;i++) {
arr[i]=scan.nextInt();
total+=arr[i];
}
if (total%2!=0) {
System.out.println("NO");
}
else {
// dfs
dfs(0,0);
if (ck) System.out.println("YES");
else System.out.println("NO");
}
}
}
2. 바둑이 승차 (dfs)
문제 풀이
- dfs로 해당 원소 사용한다, 안한다로 풀이
- dfs 인자로 (int l, int hap)을 이용
- hap을 이용하기 때문에 check 배열 필요 없음
- flag를 이용해서 구할려는 수가 제한 값보다 크면 flag를 true로 변경함 -> 가지치기
코드
package inflearn.section8;
import java.util.*;
public class 바둑이승차 {
static boolean flag; // 시간 단축
static int n;
static int arr[];
static int c;
static int max;
public static void dfs(int l, int hap) {
if (flag) return; // 시간 단축
if (l==n) {
if (hap>c) return; // 사용 불가
else if (max<hap){
max=hap; // 사용 가능, max값 갱신
}
}
else {
dfs(l+1,hap+arr[l]); // 사용
dfs(l+1,hap); // 안사용
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
c=scan.nextInt();
n=scan.nextInt();
max=0;
arr=new int[n];
for (int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
dfs(0,0);
System.out.println(max);
}
}
최대 점수 구하기
문제 풀이
- 최대 점수는 계속 갱신될수 있기 때문에 flag를 사용못함
- 지속적으로 갱신되기 때문에 time>maxTime일때만 return으로 종료 (가지치기)
package inflearn.section8;
import java.util.*;
//5 20
//10 5
//25 12
//15 8
//6 3
//7 4
public class 최대점수구하기 {
static int maxTime;
static int n;
static int max; // 점수 최종합
static int arr[];
static int timeArr[];
public static void dfs(int l, int hap, int time) {
if (time>maxTime) return; // 시간 단축을 위해 위로 이동
if (l==n) {
if (hap>max) {
max=hap; // 갱신
}
}
else {
dfs(l+1,hap+arr[l],time+timeArr[l]); // 사용
dfs(l+1,hap,time); // 안사용
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
maxTime=scan.nextInt();
max=0;
arr=new int[n];
timeArr=new int[n];
for (int i=0;i<n;i++){
arr[i]=scan.nextInt();
timeArr[i]=scan.nextInt();
}
// System.out.println("출력");
// System.out.println(Arrays.toString(arr));
// System.out.println(Arrays.toString(timeArr));
dfs(0,0,0);
System.out.println(max);
}
}
동전 교환
문제 풀이
- 제한된 배열이 아니고 무한정 쓸수 있다는 점에서 -> 사용한다, 안한다가 아닌 n개 만큼 for문이 뻗어나가는 점을 생각
- dfs(int l, int hap)을 이용
- l은 해당 원소의 사용 개수 - 종료 조건은 hap이 target과 맞을떄임.
- dfs(int l, int hap)을 이용
- 시간 단축을 위해서 가장 값이 큰 것부터 사용하는 방법을 사용
- Collections.sort()
- 가지치기
- l이 answer보다 크면 -> 더 이상 진행할 필요 없음 -> 가지치기
- 만약 target과 맞으면 answer값과 l을 비교해서 갱신하기
- 초기 answer값은 가장 큰 값으로 설정
package inflearn.section8;
import java.util.*;
//3
//1 2 5
//15
public class 동전교환 {
static int n;
static int target;
static Integer arr[];
static int answer;
public static void dfs(int l, int hap) {
if (answer<l) return;
if (hap>target) return; // 더이상 할 필요도 없음.
else if (hap==target) {
if (l<answer) answer=l; // 갱신
}
else {
for (int i=0;i<n;i++) {
dfs(l+1,hap+arr[i]);
}
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
arr=new Integer[n];
for (int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
target=scan.nextInt();
Arrays.sort(arr,Collections.reverseOrder());
answer=1000000;
dfs(0,0);
System.out.println(answer);
}
}
순열
- check 배열 사용 (n개 만큼)
- dfs 이용, check배열에서 i번째를 사용하지 않을때만 사용
- 사용하고 0으로 풀어줌
package inflearn.section8;
import java.util.*;
//3 2
//3 6 9
public class 순열 {
static int arr[];
static int check[];
static int ans[];
static int n;
static int m;
public static void dfs(int l) {
if (l==m) {
// 종료
System.out.println(Arrays.toString(ans));
}
else {
for (int i=0;i<n;i++) {
if (check[i]==0) { // 원소 사용 여부, 사용 안했으면
check[i]=1; // 원소 사용을 1로 처리
ans[l]=arr[i]; //답에는 i번째 원소를 넣어줌
dfs(l+1); // 다음으로 진행
check[i]=0; // 다시 풀어줌 (다시 사용하기 위해서)
}
}
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
arr=new int[n];
check=new int[n]; // 원소 사용 여부
ans=new int[m];
for (int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
dfs(0);
}
}
조합의 경우의 수 구하기
문제 풀이
- 메모제이션, DFS를 이용해서 조합의 경우의 수 구하기
- 메모제이션의 가지치기로 더 빠르게 구하기
- dy[n][r] >0 return ; -> 이미 구한 수이므로 더 구할 필요 없음.
package inflearn.section8;
import java.util.*;
// 메모제이션 + 조합의 DFS를 이용
public class 조합의경우의수 {
static int dy[][];
static int n;
static int m;
public static int dfs(int n, int r) {
if (dy[n][r]>0) return dy[n][r]; // 가지치기로 더 빠르게
// 종료 조건
if (n==r || r==0) return dy[n][r]=1;
else {
return dy[n][r]=dfs(n-1,r-1)+dfs(n-1,r);
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
dy=new int[35][35]; // 최대한 크게 잡음
dfs(n,m);
System.out.println(dy[n][m]);
}
}
미로 탐색할 수 있는 경우의 수
풀이 방법
- dfs로 풀이
- 도착지에 도착하였으면 answer++
- 방문처리 후 진행 -> 방문 완료하였으면 dfs, 다시 그리고 check 배열 0으로 풀어줌 -> 다시 가게
- 첫번째 지점은 반드시 방문처리 후 진행
package inflearn.section8;
import java.util.*;
public class 미로탐색 {
static int dx[]={0,1,0,-1};
static int dy[]={1,0,-1,0};
static int check[][];
static int map[][];
static int answer;
static int n;
static void dfs(int i,int j) {
if (i==n-1 && j==n-1) { // 종료
// 목적지에 도착했으면 answer 1 증가
answer++;
}
else {
// dfs
for (int k=0;k<4;k++) {
int nx=i+dx[k];
int ny=j+dy[k];
if (nx>=0 && nx<=n-1 && ny>=0 && ny<=n-1) {
if (map[nx][ny]==0 &&check[nx][ny]==0) { // map이 0인곳만 갈수 있음
check[nx][ny]=1; // 방문 처리
dfs(nx,ny); // dfs 진행
check[nx][ny]=0; // 방문 완료 후 풀어줌, 다시 가게
}
}
}
}
}
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
n=7;
check=new int[n][n];
map=new int[n][n];
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
map[i][j]=scan.nextInt();
}
}
answer=0;
check[0][0]=1;
dfs(0,0);
System.out.println(answer);
}
}
미로 최단 거리 검색
방법 1. check 배열을 통해 queue를 검사
import java.util.*;
public class Main {
static int map[][];
static int check[][];
static int n;
static int dx[]={0,1,0,-1};
static int dy[]={1,0,-1,0};
static int answer=0;
static class Point{
int x;
int y;
Point (int x, int y) {
this.x=x;
this.y=y;
}
}
public static int bfs(int x, int y) {
Queue<Point> queue=new LinkedList<>();
queue.add(new Point(x,y));
check[x][y]=1; // 방문 처리
while(!queue.isEmpty()) {
int size=queue.size();
for (int i=0;i<size;i++) {
Point point=queue.poll();
int xx=point.x;
int yy=point.y;
for (int k=0;k<4;k++) {
int nx=xx+dx[k];
int ny=yy+dy[k];
// 이 4방향이 갈 수 있으면 큐에 넣어줌
if (nx>=0 && nx<n && ny>=0 && ny<n) {
if (map[nx][ny]==0 && check[nx][ny]==0) {
check[nx][ny]=1; // 방문 처리
queue.add(new Point(nx,ny));
}
}
}
} // 4방향 순환하고 for문을 다 사용했으면 answer++증가 해주기
answer++;
// 그리고 큐 안에 도착지가 있으면 종료
for (Point point1:queue) {
if (point1.x==n-1 && point1.y==n-1) {
//System.out.println(answer);
return answer;
}
}
}
return -1;
}
public static void main(String[] args) {
n=7;
Scanner scan=new Scanner(System.in);
check=new int[n][n];
map=new int[n][n];
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
map[i][j]=scan.nextInt();
}
}
System.out.println(bfs(0,0));
}
}
방법 2. dis배열을 통해 이동할때마다 +1 증가
- map에 방문처리, 방문했으면 1로 만들어줌
- dis에 현재 이동 거리 + 1을 기록
- 마지막 위치에 해당 위치가 있으면 종료
package inflearn.section8;
import java.util.*;
public class 미로의최단거리통로2 {
static int map[][];
static int dis[][];
static int n;
static int dx[]={0,1,0,-1};
static int dy[]={1,0,-1,0};
static int answer=0;
static class Point{
int x;
int y;
Point (int x, int y) {
this.x=x;
this.y=y;
}
}
public static void bfs(int x, int y) {
Queue<Point> queue=new LinkedList<>();
queue.add(new Point(x,y));
map[x][y]=1; // map에 방문처리 (첫번쨰 방문처리)
while(!queue.isEmpty()) {
int size=queue.size();
for (int i=0;i<size;i++) {
Point point=queue.poll();
int xx=point.x;
int yy=point.y;
for (int k=0;k<4;k++) {
int nx=xx+dx[k];
int ny=yy+dy[k];
// 이 4방향이 갈 수 있으면 큐에 넣어줌
if (nx>=0 && nx<n && ny>=0 && ny<n) {
if (map[nx][ny]==0) {
map[nx][ny]=1; // map에 방문처리
dis[nx][ny]=dis[xx][yy]+1; // 기존 거리에 +1
queue.add(new Point(nx,ny));
}
}
}
}
}
}
public static void main(String[] args) {
n=7;
Scanner scan=new Scanner(System.in);
dis=new int[n][n];
map=new int[n][n];
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++) {
map[i][j]=scan.nextInt();
}
}
bfs(0,0);
if (dis[n-1][n-1]==0) {
System.out.println(-1);
}
else {
System.out.println(dis[n-1][n-1]);
}
}
}
BackEnd Developer