My Dev Blog

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번 전쟁 - 전투

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[ny][nx] = Math.max(dp[ny][nx], arr[ny][nx] + dp[a][b]);
			dfs(ny, nx); // 24, 25라인 순서 잘 생각하자 dfs는 한 번 들어가면 그대로 쭉 들어가
		}
	}
	
	public static void dynamicProgramming() {
		dp[0][0] = arr[0][0];
		dfs(0,0);
		
		for (int i = 0; i < dp.length; i++) {
			
			for (int j = 0; j < dp[i].length; j++) {
				System.out.print(dp[i][j] + " ");
			}
			System.out.println();
		}
	}

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

백준 DP 11048번 이동하기

import java.util.*;

public class Solution {

	// 보물 - Greedy 1026번
	
	public static int minVal(int n, int[] arrA, int[] arrB) {
		
		int[] arrTempA = arrA;
		
		Integer[] tempB = Arrays.stream(arrB).boxed().toArray(Integer[]::new);
		
		Arrays.sort(tempB, Collections.reverseOrder());
		
		int[] arrTempB = Arrays.stream(tempB).mapToInt(Integer::intValue).toArray();
		
		Arrays.sort(arrTempA);
		
		int numVal = 0;
		
//		for (int i = 0; i < arrTempA.length; i++) {
//			System.out.print(arrTempA[i]);
//		}
//		
//		for (int i = 0; i < arrTempB.length; i++) {
//			System.out.print(arrTempB[i]);
//		}
		
		for (int i = 0; i < n; i++) {
			numVal += (arrTempA[i] * arrTempB[i]);
		}
		
		return numVal;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		5
//		1 1 1 6 0
//		2 7 8 3 1
		// 답 18
//		int n = 5;
//		int[] arrA = {1, 1, 1, 6, 0};
//		int[] arrB = {2, 7, 8, 3, 1};
		
//		3
//		1 1 3
//		10 30 20
		// 답 80
		
		int n = 3;
		int[] arrA = {1, 1, 3};
		int[] arrB = {10, 30, 20};
		
		System.out.println(minVal(n, arrA, arrB));
	}
}

백준 Greedy 1026번 보물

public class Solution {
	
	// 쌍둥이 빌딩 숲
	// 전체 쌍둥이 빌딩의 수, 측면에서 봤을 때 보이는 빌딩의 수 [경우의 수]
	// 가장 높은 쌍둥이 빌딩부터 순서대로 배치
	// 1, 1 = 11 [1개]

	// 2, 1 = 1221, 1122 [2개] 1 * 2
	// 2, 2 = 2211 [1개] 1
	
	// 3, 1 = 133221, 123321, 122331, 122133, 133122, 113322, 112332, 112233 [8개] 2 * 4
	// 3, 2 = 233211, 223311, 221331, 221133, 331221, 331122 [6개] 1 * 4 + 2
	// 3, 3 = 332211 [1개] 1
	
	// 4, 1 = [48개] 8 * 6
	// 4, 2 = [44개] 6 * 6 + 8
	// 4, 3 = [12개] 1 * 6 + 6
	// 4, 4 = [1개] 1
	
	// 5, 1 = [384개] 48 * 8
	// 5, 2 = [400개] 44 * 8 + 48
	// 5, 3 = [140개] 12 * 8 + 44
	// 5, 4 = [20개] 1 * 8 + 12
	// 5, 5 = [1개] 1
	
	// (x, y)를 전체 쌍둥이 빌딩 x개 중, 측면에서 봤을 때 y개의 빌딩이 보이는 경우의 수라고 했을 때
	// (1, 1)은 1로 고정
	// x는 2 이상이고, y가 1일 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y) * (2 * (x - 1))
	// x는 2 이상이고, y가 1보다 크고 x보다 작을 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y) * (2 * (x - 1)) + (x - 1, y - 1)
	// x는 2 이상이고, y가 x일 때 (x, y)를 만드는 방법 => (x, y) = (x - 1, y - 1)
	
	// 11 (가장 높은 쌍둥이 빌딩 11 배치)
	// ☆☆ 1 ☆☆ 1 ☆☆ (다음으로 높은 쌍둥이 빌딩 배치할 위치 찾기)
	// 22 11 (다음으로 높은 빌딩 22를 제일 앞에 배치 시 보이는 건물 + 1, 경우의 수는 배치 전 그대로)
	// 1 22 1, 11 22 (다음으로 높은 빌딩 22를 빌딩 사이 또는 제일 뒤에 배치 시 보이는 건물 그대로, 경우의 수는 배치 전 * 2
	// 다음으로 높은 빌딩 33을 제일 앞에 배치 시 => 보이는 건물 + 1, 경우의 수는 배치 전 그대로
	// 2211(하나의 예) => 332211
	// 다음으로 높은 빌딩 33을 빌딩 사이 또는 제일 뒤에 배치 시 => 보이는 건물 그대로, 경우의 수는 배치 전 * (2 * (배치 후 쌍둥이 빌딩의 수 - 1))
	// 2211(하나의 예) => 233211, 223311, 221331, 221133
	
	// 3, 1의 경우의 수는 2, 1의 경우의 수에서만 생각 (2, 2는 이미 빌딩 2개가 보이는 상태)
	// 2, 1이 3, 1이 되기 위해서는 쌍둥이 빌딩 한 쌍을 추가로 배치하면서 보이는 건물은 그대로여야 한다. => 사이 또는 제일 뒤에 배치
	// 2, 1의 경우인 1221, 1122 경우의 수 2에 * (2 * (3 - 1)) => 3, 1 = 8개
	// 3, 2의 경우의 수는 2, 2의 경우의 수에서 사이 또는 제일 뒤에 배치, 2, 1의 경우의 수에서 제일 앞에 배치 (2가지 경우가 존재)
	// 2, 2의 경우인 2211 경우의 수 1에 * (2 * (3 - 1)) => 4
	// 2, 1의 경우인 1221, 1122 경우의 수 2 그대로
	// 3, 2 => 6개
	// 3, 3의 경우의 수는 2, 2의 경우의 수에서만 생각, 제일 앞에 배치 => 2, 2의 경우인 2211 경우의 수 1 그대로 (332211)
	
	public static int solution(int n, int count) {
		long[][] arr = new long[n + 1][n + 1];
		long preventOutOfRange = 1000000007;
		long temp = 0;
		
		arr[1][1] = 1;
		
		for (int x = 2; x <= n; x++) { // x는 2 이상
			
			for (int y = 1; y <= x; y++) {
				
				if (y == 1) { // y가 1일 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y] * (2 * (x - 1));
					temp = arr[x - 1][y] * (2 * (x - 1));
				} else if (y > 1 && y < x) { // y가 1보다 크고 x보다 작을 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y] * (2 * (x - 1)) + arr[x - 1][y - 1];
					temp = arr[x - 1][y] * (2 * (x - 1)) + arr[x - 1][y - 1];
				} else { // y가 x일 때 arr[x][y]를 만드는 방법 => arr[x][y] = arr[x - 1][y - 1];
					temp = arr[x - 1][y - 1];
				}
				
				arr[x][y] = temp % preventOutOfRange;
			}
		}
		
		return (int) arr[n][count];
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 3;
		int count = 1;
		
		System.out.println(solution(n, count)); // 8
	}
}

(x, y)를 전체 쌍둥이 빌딩 x개 중, 측면에서 봤을 때 y개의 빌딩이 보이는 경우의 수라고 했을 때

(1, 1)은 1로 고정

x는 2 이상이고, y가 1일 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y) * (2 * (x - 1))

x는 2 이상이고, y가 1보다 크고 x보다 작을 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y) * (2 * (x - 1)) + (x - 1, y - 1)

x는 2 이상이고, y가 x일 때 (x, y)를 만드는 방법

=> (x, y) = (x - 1, y - 1)

프로그래머스 쌍둥이 빌딩 숲 문제 풀이 Java

public class Solution {
	
	// 순위
	// Floyd Warshall 알고리즘으로 풀이
	
	public static int solution(int n, int[][] results) {
		int answer = 0;
		int zeroCnt = 0;
		int[][] board = new int[n][n]; // 0 ~ 4
		
		for (int i = 0; i < results.length; i++) {
			// {4, 3}의 경우
			board[results[i][0] - 1][results[i][1] - 1] = 1; // 4는 3에게 이겼으므로 board[3][2] = 1
			board[results[i][1] - 1][results[i][0] - 1] = -1; // 3은 4에게 졌으므로 board[2][3] = -1
		}
		
//		0 : {0, 1, 0, 0, 0}
//		1 : {-1, 0, -1, -1, 1}
//		2 : {0, 1, 0, -1, 0}
//		3 : {0, 1, 1, 0, 0}
//		4 : {0, -1, 0, 0, 0}
		
		for (int k = 0; k < n; k++) {
			
			for (int i = 0; i < n; i++) {
				
				for (int j = 0; j < n; j++) {
					
					if (k == i || i == j || k == j) { // 자기 자신과의 경기는 있을 수 없다.
						continue;
					}
					
					if (board[i][j] == 0) { // i와 j의 경기 결과를 분실했다면
						
						if (board[i][k] == 1 && board[k][j] == 1) { // i가 k에게 이기고, k가 j에게 이겼다면
							board[i][j] = 1; // i는 j에게 이긴 것으로 체크
						} else if (board[i][k] == -1 && board[k][j] == -1) { // i가 k에게 지고, k가 j에게 졌다면
							board[i][j] = -1; // i는 j에게 진 것으로 체크
						}
					}
				}
			}
		}
		
//		0 : {0, 1, 0, 0, 1}
//		1 : {-1, 0, -1, -1, 1} // 자기 자신을 제외하고 다른 모든 선수들과의 경기 결과를 알 수 있는 선수
//		2 : {0, 1, 0, -1, 1}
//		3 : {0, 1, 1, 0, 1}
//		4 : {-1, -1, -1, -1, 0} // 자기 자신을 제외하고 다른 모든 선수들과의 경기 결과를 알 수 있는 선수
		
		for (int i = 0; i < n; i++) {
			
			zeroCnt = 0;
			
			for (int j = 0; j < n; j++) {
				
				if (board[i][j] == 0) {
					zeroCnt++;
				}
			}
			
			if (zeroCnt == 1) {
				answer++;
			}
		}

		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};
		
		System.out.println(solution(n, results)); // 2
	}
}

프로그래머스 순위 문제 풀이 Java

import java.util.HashMap;

public class Solution {
	
	// 롤케이크 자르기
	
	public static int solution(int[] topping) {
		int answer = 0;
		
		HashMap<Integer, Integer> hm1 = new HashMap<>();
		HashMap<Integer, Integer> hm2 = new HashMap<>();
		
		for (int i = 0; i < topping.length; i++) {
			hm2.put(topping[i], hm2.getOrDefault(topping[i], 0) + 1);
		}
		
		// hm2 : {1=4, 2=2, 3=1, 4=1}
		
		for (int i = 0; i < topping.length; i++) {
			hm1.put(topping[i], hm1.getOrDefault(topping[i], 0) + 1);
			
			if (hm2.containsKey(topping[i])) {
				hm2.put(topping[i], hm2.get(topping[i]) - 1);
			}
			
			if (hm2.get(topping[i]) == 0) {
				hm2.remove(topping[i]);
			}
			
			if (hm1.size() == hm2.size()) { // hm1 : {1=2, 2=1, 3=1}, hm2 : {1=2, 2=1, 4=1} // hm1 : {1=3, 2=1, 3=1}, hm2 : {1=1, 2=1, 4=1}
				answer++;
			}
		}
		
		return answer;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] topping = {1, 2, 1, 3, 1, 4, 1, 2}; // 1, 2, 1, 3과 1, 4, 1, 2로 잘랐을 떄, 1, 2, 1, 3, 1과 4, 1, 2로 잘랐을 때
		
		System.out.println(solution(topping)); // 2
	}
}

프로그래머스 롤케이크 자르기 문제 풀이 Java

import java.util.ArrayList;
import java.util.HashMap;

public class Solution {
	
	// 양과 늑대
	
	static int maxSheepCnt;
	static HashMap<Integer, ArrayList<Integer>> hm;
	
	public static void dfs(int currentIndex, int s, int w, ArrayList<Integer> indexList, int[] info) {
		
		if (info[currentIndex] == 0) {
			s += 1;
		} else {
			w += 1;
		}
		
		if (s <= w) return;
		
		maxSheepCnt = Math.max(maxSheepCnt, s);
		
		ArrayList<Integer> nextIndexList = new ArrayList<>();
		nextIndexList.addAll(indexList);
		
		if (hm.containsKey(currentIndex)) {
			nextIndexList.addAll(hm.get(currentIndex));
		}
		
		nextIndexList.remove(Integer.valueOf(currentIndex));
		
		for (int nextIndex : nextIndexList) {
			dfs(nextIndex, s, w, nextIndexList, info);
		}
		
		return;
	}
	
	public static int solution(int[] info, int[][] edges) {
		maxSheepCnt = 0;
		hm = new HashMap<>();
		
		for (int i = 0; i < edges.length; i++) {
			
			if (!hm.containsKey(edges[i][0])) {
				hm.put(edges[i][0], new ArrayList<>());
			}
			
			hm.get(edges[i][0]).add(edges[i][1]);
		}
		
//		hm : {0=[1, 8], 1=[2, 4], 4=[3, 6], 6=[5], 8=[7, 9], 9=[10, 11]}
		
		ArrayList<Integer> startIndexList = new ArrayList<>();
		startIndexList.add(0);
		
		dfs(0, 0, 0, startIndexList, info);
		
		return maxSheepCnt;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] info = {0,0,1,1,1,0,1,0,1,0,1,1};
		int[][] edges = {{0,1},{1,2},{1,4},{0,8},{8,7},{9,10},{9,11},{4,3},{6,5},{4,6},{8,9}};
		
		System.out.println(solution(info, edges));
	}
}

프로그래머스 양과 늑대 문제 풀이 Java

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

public class Solution {
	
	// 아이템 줍기
	
	public static int solution(int[][] rectangle, int characterX, int characterY, int itemX, int itemY) {
		int answer = 0;
		int[][] board = new int[101][101]; // 전체 영역
		boolean[][] visited = new boolean[101][101]; // 방문한 좌표인지 확인을 위한 2차원 boolean 배열
		int[] dx = {0, 0, -1, 1}; // 상, 하, 좌, 우 이동에서 x 좌표 증감 값
		int[] dy = {1, -1, 0, 0}; // 상, 하, 좌, 우 이동에서 y 좌표 증감 값
		
		// STEP 1. 모든 사각형의 모서리 영역과 내부 영역을 1로 채운다.
		for (int i = 0; i < rectangle.length; i++) {
			
			int[] eachRectangle = rectangle[i]; // 하나의 사각형 꼭지점 정보가 담긴 배열
			
			// 그림1의 문제를 해결하기 위해 모든 좌표 값의 크기를 2배로 해준다.
			for (int x = eachRectangle[0] * 2; x <= eachRectangle[2] * 2; x++) {
				
				for (int y = eachRectangle[1] * 2; y <= eachRectangle[3] * 2; y++) {
					board[x][y] = 1;
				}
			}
		}
		
		// STEP 2. 모서리 영역을 제외한 내부 영역을 0으로 채운다.
		for (int i = 0; i < rectangle.length; i++) {
			
			int[] eachRectangle = rectangle[i]; // 하나의 사각형 꼭지점 정보가 담긴 배열
			
			// 시작 꼭지점 좌표 + 1 ~ 마지막 꼭지점 좌표 - 1까지 0으로 채우면 사각형 내부 영역이 0으로 채워지게 된다.
			for (int x = eachRectangle[0] * 2 + 1; x <= eachRectangle[2] * 2 - 1; x++) {
				
				for (int y = eachRectangle[1] * 2 + 1; y <= eachRectangle[3] * 2 - 1; y++) {
					board[x][y] = 0;
				}
			}
		}
		
		// STEP 3. 캐릭터의 이동 정보를 담을 클래스 CharacterPosition에 캐릭터 초기값 세팅
		CharacterPosition characterPosition = new CharacterPosition(characterX * 2, characterY * 2, 0);
		
		// STEP 4. BFS 수행
		Queue<CharacterPosition> q = new LinkedList<>();
		
		q.add(characterPosition);
		
		visited[characterX * 2][characterY * 2] = true;
		
		while (!q.isEmpty()) {
			CharacterPosition tempCharacterPosition = q.poll();
			
			if (tempCharacterPosition.x == itemX * 2 && tempCharacterPosition.y == itemY * 2) { // 캐릭터가 아이템 위치에 도달했다면
				answer = tempCharacterPosition.moveCnt / 2;
				break;
			}
			
			for (int i = 0; i < 4; i++) { // 상, 하, 좌, 우 이동
				int nextX = dx[i] + tempCharacterPosition.x;
				int nextY = dy[i] + tempCharacterPosition.y;
				
				// 직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다. 이 조건에 의해 2배 값인 2부터 100까지가 캐릭터의 이동 가능 범위가 된다.
				if (nextX < 2 || nextX > 100 || nextY < 2 || nextY > 100) {
					continue;
				}
				
				if (!visited[nextX][nextY] && board[nextX][nextY] == 1) { // 방문하지 않은 모서리 영역이라면
					q.offer(new CharacterPosition(nextX, nextY, tempCharacterPosition.moveCnt + 1));
					visited[nextX][nextY] = true;
				}
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[][] rectangle = {{1,1,7,4},{3,2,5,5},{4,3,6,9},{2,6,8,8}};
		int characterX = 1;
		int characterY = 3;
		int itemX = 7;
		int itemY = 8;
		
		// 전체 영역을 만들고, 모든 사각형의 모서리 영역과 내부 영역을 1로 채운 후, 내부 영역만 다시 0으로 채워 모서리에 남은 값 1을 따라서 좌표 이동을 하도록 만들면 된다.
		// 아래 그림1을 보면 서로 떨어져 있는 사각형이지만 두 모서리의 간격이 1이기 때문에 1을 따라서 좌표 이동을 할 경우 두 사각형이 붙어있는 것으로 인식하는 문제가 발생한다.
		// 모든 사각형의 좌표, 캐릭터의 좌표, 아이템의 좌표를 x2 하여 문제를 해결할 수 있다.
		// 이후 총 이동 거리에서 나누기 2를 해주면 된다.
		// int[][] rectangle = {{2,2,14,8},{6,4,10,10},{8,6,12,18},{4,12,16,16}};
		// int characterX = 2;
		// int characterY = 6;
		// int itemX = 14;
		// int itemY = 16;
		// 조건을 위와 같이 바꾼 후 문제를 풀고, 결과 값의 1/2을 답으로 제출하면 된다.
		
		System.out.println(solution(rectangle, characterX, characterY, itemX, itemY));
	}
}

public class CharacterPosition {
	int x = 0;
	int y = 0;
	int moveCnt = 0;
	
	public CharacterPosition(int x, int y, int moveCnt) {
		this.x = x;
		this.y = y;
		this.moveCnt = moveCnt;
	}
}

프로그래머스 아이템 줍기 문제 풀이 Java