개발 다이어리

코드

import java.util.LinkedList;
import java.util.Queue;

class 섬나라아일랜드BFS {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	static Queue<Point> q = new LinkedList<섬나라아일랜드BFS.Point>();
	
	
	static void BFS(int[][] board,int x, int y) {
		
		q.offer(new Point(x, y));
		while(!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Point p = q.poll();
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					if(nx>=0&&nx<n && ny>=0&&ny<n && board[nx][ny]==1) {
						board[nx][ny] = 99;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}
		
		
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					BFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	static  class Point{
		int x,y;

		public Point(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args){
		섬나라아일랜드BFS T = new 섬나라아일랜드BFS();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

단순히 DFS=>BFS로 해결한 코드

코드

class 섬나라아일랜드 {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1) {
				board[nx][ny] = 0;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 0;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
 0  0  0  0  0  1  0 
 0  0  0  0  1  1  0 
 0  0  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 1  1  0  0  0  0  0 
 1  0  0  0  0  0  0 
 1  0  1  0  0  0  0 

===4번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  1  0  0  0  0 

===5번 섬지우기===
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 
 0  0  0  0  0  0  0 

5

주어진 2차원 배열(지도)에 1 표기가 섬이다. 섬은 상하좌우 좌상우상좌하우하 이렇게 8방향으로 연결되어 있다.

solution은 지도를 순회하여 섬을 탐색한다.

DFS는 섬을 지도에서 소거한다. 이렇게 되면 자연스럽게 solution이 다시 순회를 시작해도 같은 섬 중복이 날수가 없다.

여기서는 1이면 섬으로 판단한다. 그래서 가시성을 위해 지워진 섬을 99로 변경해 어떻게 동작하는지 좀 더 명확하게 볼 수 있다.

코드

class 섬나라아일랜드 {
	static int answer=0, n;
	static int[] dx={-1, -1, 0, 1, 1, 1 , 0 , -1};
	static int[] dy={0 , 1 , 1, 1, 0, -1, -1, -1};
	
	static void DFS(int[][] board,int x, int y) {
		for (int i = 0; i < dx.length; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			if(nx>=0 && nx<n &&ny >=0 &&ny <n &&board[nx][ny]==1 ) {
				board[nx][ny] = 99;
				DFS(board,nx,ny);
			}
			
		}
	}
	public void solution(int[][] board){
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==1) {
					answer++;
					board[i][j] = 99;
					DFS(board, i, j);
					
					System.out.println("==="+answer+"번 섬지우기===");
					for(int[] a : board) {
						for(int b : a) {
							System.out.printf("%2s ",b);
						}
						System.out.println();
					}
					System.out.println();
				}
			}
		}
	}
	

	public static void main(String[] args){
		섬나라아일랜드 T = new 섬나라아일랜드();
		int[][] arr=
				{{1, 1, 0, 0, 0, 1, 0}
				,{0, 1, 1, 0, 1, 1, 0}
				,{0, 1, 0, 0, 0, 0, 0}
				,{0, 0, 0, 1, 0, 1, 1}
				,{1, 1, 0, 1, 1, 0, 0}
				,{1, 0, 0, 0, 1, 0, 0}
				,{1, 0, 1, 0, 1, 0, 0}};
		
		
		n= arr.length;
		T.solution(arr);
		System.out.println(answer);
	}
}

결과

===1번 섬지우기===
99 99  0  0  0  1  0 
 0 99 99  0  1  1  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===2번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0  1  0  1  1 
 1  1  0  1  1  0  0 
 1  0  0  0  1  0  0 
 1  0  1  0  1  0  0 

===3번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
 1  1  0 99 99  0  0 
 1  0  0  0 99  0  0 
 1  0  1  0 99  0  0 

===4번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0  1  0 99  0  0 

===5번 섬지우기===
99 99  0  0  0 99  0 
 0 99 99  0 99 99  0 
 0 99  0  0  0  0  0 
 0  0  0 99  0 99 99 
99 99  0 99 99  0  0 
99  0  0  0 99  0  0 
99  0 99  0 99  0  0 

5

코드

import java.util.*;

class Main {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int n, m;
	static Queue<Point> Q=new LinkedList<>();
	
	static void BFS2(){
		
		while(!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				Point p = Q.poll();
				
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j];
					int ny = p.y+dy[j];
					
					if(nx>=0&&nx<n  && ny>=0&&ny<m && board[nx][ny]==0) {
						board[nx][ny]= 1;
						Q.offer(new Point(nx, ny));
						dis[nx][ny] =dis[p.x][p.y]+1;
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		m=6; //가로 크기
		n=4; //세로 크기
		board=new int[n][m];
		dis=new int[n][m];
		
		int[][] tmp = 
			{{0, 0, -1, 0, 0, 0}
			,{0, 0, 1, 0, -1, 0}
			,{0, 0, -1, 0, 0, 0}
			,{0, 0, 0, 0, -1, 1}};
		
		board = tmp.clone();
		
		for(int i=0; i<n; i++){
			for(int j=0; j<m; j++){
				if(board[i][j]==1) Q.offer(new Point(i, j));
				//출발점이 여러개라 미리 넣어둠
			}
		}
		
		BFS2();
		
		//0이 하나라도 존재하면 토마토가 모두 익지 못하는 상황
		long count = Arrays.stream(board)
		      .flatMapToInt(Arrays::stream)
		      .filter(value->value==0)
		      .count();
		if(count>0) System.out.println(-1);
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board[i].length; j++) {
				if(board[i][j]==0) {
					System.out.println(-1);
					return;
				}
			}
		}
		
		// 만약 처음부터 모두 익어있다면 자연스럽게 0 출력될 것
		int value = Integer.MIN_VALUE;
		for (int i = 0; i < dis.length; i++) {
			for (int j = 0; j < dis[i].length; j++) {
				value = Math.max(value, dis[i][j]);
			}
		}
		System.out.println(value);
		for (int[] arr : dis) {
			for (int val : arr) {
				System.out.printf("%2s ",val);
			}
			System.out.println();
		}
		
	}
	static class Point{
		public int x, y;
		Point(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}

결과

4
 3  2  0  2  3  3 
 2  1  0  1  0  2 
 3  2  0  2  2  1 
 4  3  4  3  0  0

전부 똑같다. 다른 점은 시작점이 여러 개라면 미리 큐에 넣어둔다. 그 차이가 전부다.

문제에서 시작점인 것에 위치값을 준게 아니라 미리 board[x][y] = 1 같이 넣어뒀기에 시작 시 출발 값에 1을 체크할 필요 없다.

코드

import java.util.*;

class 미로의차단거리통로BFS {
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	static int[][] board, dis;
	static int cnt = 0;
	static int answer = Integer.MAX_VALUE;
	
	static void BFS(int x, int y){
		Queue<Point> Q=new LinkedList<>();
		Q.offer(new Point(x, y));
		board[x][y]=1;
		while(!Q.isEmpty()){
			Point tmp=Q.poll();
			for(int i=0; i<4; i++){
				int nx=tmp.x+dx[i];
				int ny=tmp.y+dy[i];
				if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
					board[nx][ny]=1;
					Q.offer(new Point(nx, ny));
					dis[nx][ny]=dis[tmp.x][tmp.y]+1;
				}
			}
		}	
	}
	
	
	static void BFS3(int x,int y) {
		Queue<Point> q = new LinkedList<Point>();
		q.offer(new Point(x, y));
		board[x][y]=1;
		while(!q.isEmpty()) {
			int size = q.size();
			//Q 순회용 
			for (int i = 0; i < size; i++) {
				Point p = q.poll();
				// Q 요소의 다음 갈 곳 순회용
				for (int j = 0; j < dx.length; j++) {
					int nx = p.x+dx[j]; //다음갈 곳
					int ny = p.y+dy[j];
					if(nx>=1&&nx<=7 && ny>=1&&ny<=7 &&board[nx][ny]==0) {
						board[nx][ny] = 1;
						dis[nx][ny] = dis[p.x][p.y]+1;
						q.offer(new Point(nx, ny));
					}
				}
			}
		}
	}
	
	public static void main(String[] args){
		dis=new int[8][8];
		//인덱스 [0][n], [n][0]은 버리는 공간, 1부터 시작을 위함
		int[][] arr = 
			{ {0, 0, 0, 0, 0, 0, 0, 0}
			/*-----------------------*/
			, {0,/**/ 0, 0, 0, 0, 0, 0, 0}
			, {0,/**/ 0, 1, 1, 1, 1, 1, 0}
			, {0,/**/ 0, 0, 0, 1, 0, 0, 0}
			, {0,/**/ 1, 1, 0, 1, 0, 1, 1}
			, {0,/**/ 1, 1, 0, 0, 0, 0, 1}
			, {0,/**/ 1, 1, 0, 1, 1, 0, 0}
			, {0,/**/ 1, 0, 0, 0, 0, 0, 0} };
		
		board = arr.clone();
		
		BFS3(1, 1);
		for(int[] y : dis) {
			for (int x : y) {
				System.out.printf("%2s ", x);
			}
			System.out.println();
		}
		if(dis[7][7]==0) System.out.println(-1); //목적지 도달 불가
		else System.out.println(dis[7][7]);
	}
}

class Point{
	public int x, y;
	Point(int x, int y){
		this.x=x;
		this.y=y;
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return x+":"+y;
	}
}

결과

 0  0  0  0  0  0  0  0 
 0  0  1  2  3  4  5  6 
 0  1  0  0  0  0  0  7 
 0  2  3  4  0 10  9  8 
 0  0  0  5  0  9  0  0 
 0  0  0  6  7  8  9  0 
 0  0  0  7  0  0 10 11 
 0  0  9  8  9 10 11 12 
12

최단 거리는 DFS가 아닌 BFS를 쓰는 것이 맞다. 

DFS도 가능하지만 모든 경우의 수를 끝까지 탐색해야만 최단 거리임을 보증할 수 있다.

반면에 BFS는 가장 먼저 발견한 것이 최단거리임을 보장한다.

코드

class 미로탐색DFS {
	//다음 방향을 결정
	static int[] dx={-1, 0, 1, 0};
	static int[] dy={0, 1, 0, -1};
	
	static int[][] board; 
	static int[][] path;  // 경로 확인용
	static int answer=0;
	static int cnt=1;

	static void DFS2(int x, int y){
		if(x==7 && y==7) {
			answer++;

			System.out.println(answer+"번 째 경로");
			for (int i = 0; i < path.length; i++) {
				for (int j = 0; j < path[i].length; j++) {
					if(i==0||j==0) {
						System.out.printf("%2s",i==0?"--":"|");
						continue;
					}
					System.out.printf("%2s",path[i][j]==0?"":path[i][j]+"");
				}
				System.out.println();
			}
			System.out.println();
			
			return;
		} else {
			for (int i = 0; i < dx.length; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				if(1<=nx&&nx<=7&&1<=ny&&ny<=7 && board[nx][ny]==0) {
					cnt++;
					board[nx][ny] =1;
					path[nx][ny] =cnt;
					
					DFS2(nx,ny);
					
					board[nx][ny] =0;
					path[nx][ny] =0;
					cnt--;
				}
			}
		}
	}
	
	public static void main(String[] args){
		path=new int[8][8];
		//인덱스 [0][n], [n][0]은 버리는 공간, 1부터 시작을 위함
		int[][] arr = 
			{ {0, 0, 0, 0, 0, 0, 0, 0}
			/*-----------------------*/
			, {0,/**/ 0, 0, 0, 0, 0, 0, 0}
			, {0,/**/ 0, 1, 1, 1, 1, 1, 0}
			, {0,/**/ 0, 0, 0, 1, 0, 0, 0}
			, {0,/**/ 1, 1, 0, 1, 0, 1, 1}
			, {0,/**/ 1, 1, 0, 0, 0, 0, 1}
			, {0,/**/ 1, 1, 0, 1, 1, 0, 0}
			, {0,/**/ 1, 0, 0, 0, 0, 0, 0} };
		
		board = arr.clone();
		
		board[1][1]=1;
		path[1][1]=1;
		DFS2(1, 1);
		System.out.print(answer);
	}
}

결과

1번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |        1314  
 |          1516
 |            17

2번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |        1314  
 |          15  
 |          1617

3번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |    151413    
 |    16    2122
 |    1718192023

4번 째 경로
----------------
 | 1 2 3 4 5 6 7
 |             8
 |        1110 9
 |        12    
 |    151413    
 |    16        
 |    1718192021

5번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7 8 910  
 |          1112
 |            13

6번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7 8 910  
 |          11  
 |          1213

7번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7        
 |     8    1314
 |     910111215

8번 째 경로
----------------
 | 1            
 | 2            
 | 3 4 5        
 |     6        
 |     7        
 |     8        
 |     910111213

8

8개 경로가 각각 어떤 경로인지 확인

코드

import java.util.*;
class 조합구하기{
	static int[] combi;
	static int n, m;
	
	static void DFS(int L, int s) {
		if(L==m) {//L이 m과 같다면 목표 배열 크기까지 수행 후 다시 호출된 것
			//즉, L은 배열인덱스범위 밖이다.
			System.out.println(Arrays.toString(combi));
			return;
		}
		for (int i = s; i <= n; i++) {
			combi[L] = i;
			DFS(L+1, i+1);
		}
	}
	
	
	public static void main(String[] args){
		n=5; // 최대 숫자
		m=2; // 조합배열 크기
		combi=new int[m];//조합 배열
		DFS(0, 1);//배열인덱스, 시작 숫자
	}
}

결과

[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]

검증 코드

import java.util.*;
class 조합구하기{
	static int[] combi;
	static int n, m, cnt;
	
	static void DFS(int L, int s) {
		if(L==m) {//L이 m과 같다면 목표 배열 크기까지 수행 후 다시 호출된 것
			//즉, L은 배열인덱스범위 밖이다.
			cnt++;
			System.out.println(cnt+" "+"L"+L+" "+Arrays.toString(combi) +"[출력]");
			return;
		}
		for (int i = s; i <= n; i++) {
			cnt++;
			combi[L] = i;
			System.out.println(cnt+" "+"L"+L+" "+Arrays.toString(combi));
			DFS(L+1, i+1);
		}
	}
	
	
	public static void main(String[] args){
		n=5; // 최대 숫자
		m=2; // 조합배열 크기
		combi=new int[m];//조합 배열
		DFS(0, 1);//배열인덱스, 시작 숫자
	}
}

결과

1 L0 [1, 0]
2 L1 [1, 2]
3 L2 [1, 2][출력]
4 L1 [1, 3]
5 L2 [1, 3][출력]
6 L1 [1, 4]
7 L2 [1, 4][출력]
8 L1 [1, 5]
9 L2 [1, 5][출력]
10 L0 [2, 5]
11 L1 [2, 3]
12 L2 [2, 3][출력]
13 L1 [2, 4]
14 L2 [2, 4][출력]
15 L1 [2, 5]
16 L2 [2, 5][출력]
17 L0 [3, 5]
18 L1 [3, 4]
19 L2 [3, 4][출력]
20 L1 [3, 5]
21 L2 [3, 5][출력]
22 L0 [4, 5]
23 L1 [4, 5]
24 L2 [4, 5][출력]
25 L0 [5, 5]

코드

import java.util.*;

class 수열추측하기{
	static int[] b, p, ch;
	static int n, f;
	static boolean flag=false;
	static int[][] dy=new int[35][35];
	
	static int combi(int n, int r){
		if(dy[n][r]>0) return dy[n][r];
		if(n==r || r==0) return 1;
		else return dy[n][r]=combi(n-1, r-1)+combi(n-1, r);
	}
	
	static void DFS(int L, int sum){
		if(flag) return;
		if(L==n){
			if(sum==f){
				for(int x : p) System.out.print(x+" ");
				flag=true;
			}
		}else{
			for(int i=1; i<=n; i++){
				if(ch[i]==0){
					ch[i]=1;
					p[L]=i;
					DFS(L+1, sum+(p[L]*b[L]));
					ch[i]=0;
				}
			}
		}
	}

	public static void main(String[] args){
		n=4;
		f=16;
		b=new int[n];
		p=new int[n];
		ch=new int[n+1];
		for(int i=0; i<n; i++){
			b[i]=combi(n-1, i);
		}
		System.out.println(Arrays.toString(b));
		DFS(0, 0);
	}
}

결과

[1, 3, 3, 1]
3 1 2 4

미리 메모이제이션을 이용해서 경우의 수를 계산 후 이를 사용

경우의 수, nCr는 (n-1Cr-1)+ (n-1Cr) 와 같다는 공식을 사용한다.

n은 요소의 개수, r은 그 중 몇 개 선택할지

그리고 n==r 인 경우 경우의 수는 1, 요소가 3개에 3개를 선택한다면 경우의 수는 1개 뿐

r==0 인 경우도 경우의 수는 1이다, 요소가 아무리 많아도 0개를 선택할 경우의 수는 1개 뿐

6C4는 15의 경우의 수가 나온다.

코드

class 조합의경우수$메모이제이션{
	static int[][] dy=new int[35][35];
	static int cnt1,cnt2;
	
	static int DFS1(int n, int r){
		cnt1++;
		if(n==r || r==0) return 1;
		else return DFS1(n-1, r-1)+DFS1(n-1, r);
	}
	
	static int DFS2(int n, int r){
		cnt2++;
		if(dy[n][r]!=0) return dy[n][r]; //이미 계산해놓은게 있다.
		if(n==r||r==0) return 1;
		else {
			return dy[n][r]=DFS2(n-1,r-1)+DFS2(n-1,r);
		}
		
	}
	
	public static void main(String[] args){
		int n=6;
		int r=4;
		
		System.out.print("메모이제이션 사용 안함 ");
		System.out.println(DFS1(n, r)+" "+cnt1);
		System.out.print("메모이제이션 사용 함 ");
		System.out.println(DFS2(n, r)+" "+cnt2);
	}
}

결과

메모이제이션 사용 안함 15 29
메모이제이션 사용 함 15 17

숫자가 적어서 메모이제이션 효과가 미미해보이지만 아래처럼 조금만 증가해도 기하급수적으로 반복호출하게 된다.

메모이제이션 사용 안함 30045015 60090029
메모이제이션 사용 함 30045015 401

코드

import java.util.Arrays;
import java.util.Collections;

class 동전교환{
	static int n, m, answer=Integer.MAX_VALUE;
	static int sum;
	static int[] arr;
	static Integer[] arr2;
	static boolean flag;
	
	
	
	static void DFS3(int L) {
		if(flag) return;
		if(sum>m) return; // 목표값보다 크면 안된다.
		if(L>=answer) return;
		if(sum==m) {
			answer = Math.min(answer, L);
			flag = true;
			return;
		}else {
			for (int i = arr.length-1; i>=0; i--) {
				sum+=arr[i];
				DFS3(L+1);
				sum-=arr[i];
			}
		}
	}
	
	static void DFS2(int L) {
		if(flag) return;
		if(sum>m) return;
		if(L>=answer) return;
		if(sum==m) {
			answer = Math.min(answer, L);
			flag = true;
			return;
		}else {
			for (int j = 0; j < arr2.length; j++) {
				sum+= arr2[j];
				DFS2(L+1);
				sum-= arr2[j];
			}
		}
	}

	
	public static void main(String[] args){
		arr= new int[] {1,2,5};
		arr2 = Arrays.stream(arr.clone()).boxed().toArray(Integer[]::new);
		n=3;
		m=223 ;
		DFS3(0);
		System.out.println(answer);
		
		
		flag = false;
		sum = 0;
		answer = 1231;
		Arrays.sort(arr2, Collections.reverseOrder());
		DFS2(0);
		System.out.println(answer);
		
	}
}

결과

46
46

최소 동전 개수를 구하려면 큰 동전부터 낮은 동전 순으로 나눠가면 된다.

기본형 배열 정렬은 순방향만 된다. 

역방향 정렬을 하려면 참조형으로 변경해야한다.

기본형은 그래서 반복문을 뒤에서 앞으로 탐색했다.

코드

import java.util.*;


class 중복순열DFS{
	static int[] pm;
	static int n //수 크기
		     , m// m 배열 길이
	         , cnt;
	static void DFS3(int L) {
		if(L==m) {
			System.out.println(cnt+" "+Arrays.toString(pm));
			return;
		}else {
			for (int i = 1; i <= n; i++) {
				cnt++;
				pm[L] = i;
				DFS3(L+1);
			}
		}
	}
	
	public static void main(String[] args){
		n=3;
		m=2;
		pm=new int[m];
		DFS3(0);
	}
}

결과

2 [1, 1]
3 [1, 2]
4 [1, 3]
6 [2, 1]
7 [2, 2]
8 [2, 3]
10 [3, 1]
11 [3, 2]
12 [3, 3]

나머지 빈 숫자 값 추측해보기

확인 방법은?