My Dev Blog

public class Solution {

	// 이동하기 - DP 11048번
	
	static int n = 3;
	static int m = 4;
	static int[][] arr = {{1, 2, 3, 4}, {0, 0, 0, 5}, {9, 8, 7, 6}};
	static int[] dy = {1, 1, 0};
	static int[] dx = {0, 1, 1};
	static int[][] dp = new int[n][m];
	
	public static void dfs(int a, int b) {
		
		for(int i = 0; i < 3; i++) {
			int ny = a + dy[i];
			int nx = b + dx[i];
			
			if(ny > n - 1 || nx > m - 1) {
				continue;
			}
			
			// dp 갱신 후 dfs(순서 잘 생각)
			dp[ny][nx] = Math.max(dp[ny][nx], arr[ny][nx] + dp[a][b]);
			dfs(ny, nx);
		}
	}
	
	public static void dynamicProgramming() {
		dp[0][0] = arr[0][0];
		dfs(0,0);
		
		for(int i = 0; i < n; i++) {
			
			for(int j = 0; j < m; j++) {
				System.out.print(dp[i][j] + " ");
			}
            
			System.out.println();
		}
		
		System.out.println("얻을 수 있는 최대 사탕 개수 : " + dp[n - 1][m - 1]);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// (1,1) 좌상단에서 (N,M) 우하단까지 사탕 최대로 얻기
		dynamicProgramming();
	}
}

백준 DP 11048번 이동하기

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

public class Solution {

	// 미로 탐색 - BFS 2178번
	// 최단 거리 탐색 BFS
	
	static int r = 4;
	static int c = 6;
	static int[][] arr = {{1, 0, 1, 1, 1, 1}, {1, 0, 1, 0, 1, 0}, {1, 0, 1, 0, 1, 1}, {1, 1, 1, 0, 1, 1}};
	static boolean[][] visit = {};
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {-1, 1, 0, 0};
	
	public static void bfs(int n, int m) {
		
		Queue<int[]> q = new LinkedList<>();
		
		q.offer(new int[] {n,m});
		
		visit[n][m] = true;
		
		while(!q.isEmpty()) {
			
			int[] tempArr = q.poll();
			int row = tempArr[0];
			int col = tempArr[1];
			
			for(int i = 0; i < 4; i++) {
				int nextX = col + dx[i];
				int nextY = row + dy[i];
				
				if(nextX < 0 || nextY < 0 || nextX >= c || nextY >= r) {
					continue;
				}
				
				if(visit[nextY][nextX] || arr[nextY][nextX] == 0) {
					continue;
				}
				
				q.offer(new int[] {nextY,nextX});
				arr[nextY][nextX] = arr[row][col] + 1;
				visit[nextY][nextX] = true;
			}
		}
		
		System.out.println(arr[r-1][c-1]);
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		visit = new boolean[r][c];
		
		bfs(0, 0);
	}
}

백준 BFS 2178번 미로 탐색

public class Solution {
	
	// 잃어버린 괄호 - Greedy 1541번
	
	public static int solution(String str) {
		String[] strArr1 = str.split("-"); // 문자 "-" 기준으로 split
		int totalSum = 0;
		int tempSum = 0;
		
		// strArr1 = {"55", "50+40", "20", "30+40"}
		
		for (int i = 0; i < strArr1.length; i++) {
			
			tempSum = 0;
			
			String[] strArr2 = strArr1[i].split("\\+"); // 특수문자 "+" 기준으로 split (특수문자의 경우 \\특수문자 or [특수문자])
			
			for (int j = 0; j < strArr2.length; j++) {
				tempSum += Integer.parseInt(strArr2[j]);
			}
			
			if (i == 0) { // 처음 구간은 +
				totalSum += tempSum; // +55
			} else { // 이후 구간은 -
				totalSum -= tempSum; // -90-20-70
			}
		}
		
		return totalSum;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str = "55-50+40-20-30+40"; // (55)-(50+40)-(20)-(30+40) 이 값이 최소가 된다.
		
		System.out.println(solution(str)); // -125
	}
}

백준 Greedy 1541번 잃어버린 괄호

import java.util.Arrays;

public class Solution {
	
	// 줄 세우기 - DP 7570번
	// 제일 앞 또는 제일 뒤로만 이동 가능
	// 연속된 가장 긴 증가하는 부분 수열 이용
	
	static int n = 7;
	static int[] arr = {3, 7, 5, 2, 6, 1, 4};
	static int[] dp = {1, 1, 1, 1, 1, 1, 1};
	
	public static void setLine() {
		
		int clisCnt = 0;
		
		for (int i = 0; i < n; i++) {
			
			for (int j = 0; j < i; j++) {
				
				if (arr[i] == arr[j] + 1) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
		}
		
		// arr = {3, 7, 5, 2, 6, 1, 4}
		// dp = {1, 1, 1, 1, 2, 1, 2}
		
		Arrays.sort(dp);
		
		clisCnt = dp[n - 1]; // 2
		
		// 3, 4 또는 5, 6이 연속된 가장 긴 증가하는 부분 수열이므로 나머지 5개의 숫자를 이동해 1, 2, 3, 4, 5, 6, 7로 줄 세우기 가능
		System.out.println(n - clisCnt + "번의 이동만으로 줄 세우기 가능");
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		setLine();
	}
}

백준 DP 7570번 줄 세우기

import java.util.Arrays;

public class Solution {
	
	// 줄 세우기 - DP 2631번
	// 이동 위치 제한 없음
	// 가장 긴 증가하는 부분 수열(LIS) 이용
	
	static int n = 7;
	static int[] arr = {3, 7, 5, 2, 6, 1, 4};
	static int[] dp = {1, 1, 1, 1, 1, 1, 1};
	
	public static void setLine() {
		
		int lisCnt = 0;
		
		for (int i = 0; i < n; i++) {
			
			for (int j = 0; j < i; j++) {
				
				if (arr[i] > arr[j] && dp[i] <= dp[j]) {
					dp[i] = dp[j] + 1;
				}
			}
		}
		
		// arr = {3, 7, 5, 2, 6, 1, 4}
		// dp = {1, 2, 2, 1, 3, 1, 2}
		
		Arrays.sort(dp);
		
		lisCnt = dp[n - 1]; // 3
		
		// 3, 5, 6이 가장 긴 증가하는 부분 수열이므로 나머지 4개의 숫자를 이동해 1, 2, 3, 4, 5, 6, 7로 줄 세우기 가능
		System.out.println(n - lisCnt + "번의 이동만으로 줄 세우기 가능");
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		setLine();
	}
}

백준 DP 2631번 줄 세우기

public class Solution {

	// 1, 2, 3 더하기 - DP 9095번
	// n을 1, 2, 3의 합으로 나타내는 방법의 수
	
	static int n = 4;
	static int[] dp = new int[101];
	
	// 1+1+1+1
	// 1+1+2
	// 1+2+1
	// 2+1+1
	// 2+2
	// 1+3
	// 3+1
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// n은 1일 때 1
		// 2일 때 1+1, 2
		// 3일 때 1+1+1, 1+2, 2+1, 3
		
		// 4는 1+3/2+2/3+1로 나타낼 수 있음
		// 1+(1+1+1)/2+(1+1)/3+(1)
		// 1+(1+2)/2+(2)
		// 1+(2+1)
		// 1+(3)
		// 따라서 f(3)+f(2)+f(1)로 나타낼 수 있는 것이다.
		
		dp[1] = 1;
		dp[2] = 2;
		dp[3] = 4;
		
		for (int i = 4; i <= 100; i++) {
			dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
		}
		
		System.out.println(dp[n]);
	}
}

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

public class Solution {

	// 숨바꼭질 - BFS 1697번
	
	static int n = 5;
	static int m = 17;
	
	public static void bfs(int a, int b) {
		Queue<Integer> q = new LinkedList<>();
		
		int[] check = new int[100001]; // 0 ~ 17까지 만들자
		boolean[] visit = new boolean[100001];
		
		Arrays.fill(check, 0); // 전체 0으로 초기화
		
		q.offer(n); //5 넣고
		visit[n] = true; // 5 방문
		
		while (!q.isEmpty()) {
			// 5 4 6 10 3 (5) 8 (5) 7 12
			// 0 1 1 1 2 0 2 0 2 2
			int num = q.poll(); // 5 꺼내 // 4 꺼내
//				check[num] = check[num] + 1;
//				visit[num] = true; // 5 방문처리 // 4 방문처리
			
			if (num == m) {
				System.out.println(check[num]);
			}
			
			if (num < 1 || num > 50000) {
				continue;
			}
			
			if (visit[num - 1] == false) { // 4를 방문하지 않았다면 // 3을 방문하지 않았다면
				q.offer(num - 1); // 4 넣기 // 3 넣기
				check[num - 1] = Math.max(check[num - 1], check[num] + 1); // check[4] = 1이 될거야 // check[3] = 2가 될거야
				visit[num - 1] = true; // 4 방문처리 // 3 방문처리
			}
			
			if (visit[num + 1] == false) { // 6을 방문하지 않았다면 // 5는 스킵
				q.offer(num + 1); // 6 넣기
				check[num + 1] = Math.max(check[num + 1], check[num] + 1); // check[6] = 1이 될거야
				visit[num + 1] = true; // 6 방문처리
			}
			
			if (visit[num * 2] == false) { // 10을 방문하지 않았다면 // 8을 방문하지 않았다면
				q.offer(num * 2); // 10 넣기 // 8 넣기
				check[num * 2] = Math.max(check[num * 2], check[num] + 1); // check[10] = 1이 될거야 // check[8] = 2가 될거야
				visit[num * 2] = true; // 10 방문 // 8 방문
			}
		}
		
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		// 횟수의 max 카운트는 17 - 5일 거야
		// +1, -1, x2 3가지 경우에 대해 계속 bfs 수행
		bfs(n, m);
	}
}

백준 BFS 1697번 숨바꼭질

import java.util.ArrayList;

public class Solution {

	// 전쟁 - 전투 - DFS 1303번
	
	static int n = 5;
	static int m = 5;
	static char[][] arr = {{'W','B','W','W','W'}, {'W','W','W','W','W'}, {'B','B','B','B','B'}, {'B','B','B','W','W'}, {'W','W','W','W','W'}};
	static boolean[][] visit = new boolean[5][5];
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static ArrayList<Integer> wList = new ArrayList<>();
	static ArrayList<Integer> bList = new ArrayList<>();
	static int cnt = 0;
	static int wValue = 0;
	static int bValue = 0;
	
//	WBWWW
//	WWWWW
//	BBBBB
//	BBBWW
//	WWWWW
	
	public static void dfs(int i, int j) {
		
		visit[i][j] = true; // 탐색을 위해 들어왔다면 방문처리
		cnt++;
		
		for (int k = 0; k < 4; k++) {
			
			int row = i + dy[k];
			int col = j + dx[k];
			
			if (row < 0 || row > n - 1 || col < 0 || col > m - 1) {
				continue;
			}
			
			if (arr[row][col] == arr[i][j] && visit[row][col] == false) { // 팀이 같고, 아직 방문한적 없다면
				dfs(row, col);
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		for (int i = 0; i < n; i++) { // 행
			
			for (int j = 0 ; j < m; j++) { // 열
				
				if (visit[i][j] == false) { // 방문 전이라면
					cnt = 0;
					
					dfs(i, j); // 상하좌우 탐색하기 위해 dfs // 덩어리의 갯수가 결정됨
					
					if (arr[i][j] == 'W') {
						System.out.println("흰색 덩어리" + cnt);
						wList.add(cnt * cnt);
					} else if (arr[i][j] == 'B') {
						System.out.println("파란 덩어리" + cnt);
						bList.add(cnt * cnt);
					}
				}
			}
		}
		
		for (int i = 0; i < wList.size(); i++) {
			wValue += wList.get(i);
		}
		
		for (int i = 0; i < bList.size(); i++) {
			bValue += bList.get(i);
		}
		
		System.out.println("흰색 팀의 위력 : " + wValue + " 파란 팀의 위력 : " + bValue);
	}
}

백준 DFS 1303번 전쟁 - 전투