[커뮤러닝 - 테스트] 해시/DFS/BFS/동적계획법

🔎 개념

HashMap - getOrDefault()

		String [] alphabet = { "A", "B", "C" ,"A"};
		HashMap<String, Integer> hm = new HashMap<>();
		for(String key : alphabet) hm.put(key, hm.getOrDefault(key, 0) + 1);

        // 결과 : {A=2, B=1, C=1}

---

📚 위장 - Hash

import java.util.*;

public class Java0720_1 {
    public int solution(String[][] clothes) {
    	
    	HashMap<String,Integer> map = new HashMap<>();    	
    	
    	for(String[] str:clothes) map.put(str[1], map.getOrDefault(str[1], 0)+1);
    	
        int answer = 1;
        for(String key:map.keySet()) 
        	answer*=map.get(key) +1; // 안 입는 경우 +1
        
        return answer -1; // 아무것도 안 입는 경우는 없으므로 빼기
    }
	
}

📚 올바른 괄호의 갯수 - DFS

📚 게임 맵 최단거리 - BFS,DFS

최단거리 문제는 BFS로 푸는것이 효율적이다.

DFS(시간초과)

public class Java0722_1 {
	
	public static boolean[][] visited;
	public int[][] d = {{-1,0},{1,0},{0,1},{0,-1}}; 
	public int y,x,n,m,answer;
	
    public int solution(int[][] maps) {
    	
    	y=0;x=0;  	
    	n=maps.length;m=maps[0].length;
    	visited = new boolean[n][m];
    	
    	answer=10000;
    	dfs(maps,y,x,0);
    	
    	return answer==10000? -1:answer;
    }

	public void dfs(int[][] maps, int y, int x, int total) {
		
		total++;
		
		if(y==n-1&&x==m-1) {
			answer = Math.min(answer, total);
			return;
		}
		
		for(int[] dir:d) {
			
			int ny = y+dir[0],nx= x + dir[1];
			
			if(ny<0||ny>n-1||nx<0||nx>m-1) continue; // 여기서 return -1하면 진행이 안됨!
			if(visited[ny][nx]|| maps[ny][nx]==0) continue;
			
			
			visited[ny][nx] = true;
			dfs(maps,ny,nx,total);
			visited[ny][nx] =false; 
			// 방문했다가 리턴한 뒤에는 방문해제하는 것 중요!!
			
		}
		
		// return -1; 
		// 재귀되는 dfs()는 void형으로 해야함. 괜히 int형으로 해서 마지막에 이거 추가하면 -1만 나오더라..
	}
	
//	public static void main(String[] args) {
//		int[][] maps = {{1,0,1,1,1},{1,0,1,0,1},{1,0,1,1,1},{1,1,1,0,1},{0,0,0,0,1}};
//		Java0722_1 sol = new Java0722_1();
//		System.out.print(sol.solution(maps));
//	}
}

BFS

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

public class Java0722_1 {
	
	public static boolean[][] visited;
	public int[][] d = {{-1,0},{1,0},{0,1},{0,-1}}; 
	public int y,x,n,m;
	
	class Node{
		
		public Node(int y, int x, int distance) {
			this.y = y;
			this.x = x;
			this.distance = distance;
		}

		int x,y,distance;
		
	}
	
    public int solution(int[][] maps) {
    	
    	n = maps.length; m = maps[0].length;
    	y=0;x=0;
    	visited = new boolean[n][m];
    	
    	return bfs(maps,y,x);
    }

	public int bfs(int[][] maps,int y, int x) {
		
		Queue<Node> q = new LinkedList<Node>();
		q.offer(new Node(y,x,1)); // 현재 좌표,좌표까지의 거리
		visited[y][x] = true;
		
		while(!q.isEmpty()) {
			
			Node node = q.poll();
			if(node.y ==n-1 && node.x == m-1) return node.distance;
			
			for(int[] dir:d) {
				int ny = node.y + dir[0];
				int nx = node.x + dir[1];
				
				if(nx>=0&&ny>=0&&nx<n&&ny<m) {
					if(maps[ny][nx]==1 && !visited[ny][nx]) {
						visited[ny][nx] = true;
						q.offer(new Node(ny,nx,node.distance+1));
					}
				}
			}
			
		}
		return -1;
	}
 
}

📚 정수 삼각형 - DP

import java.util.Arrays;

public class Java0723_1 {
    public int solution(int[][] triangle) {
    	
    	int length = triangle.length;
    	int[][] d = new int[length][triangle[length-1].length];
    	
    	d[0][0] = triangle[0][0];
    	for(int i=0;i<length-1;i++) {
    		for(int j=0;j<triangle[i].length;j++) {
        		d[i+1][j] = Math.max(d[i+1][j],d[i][j]+triangle[i+1][j]);			
        		d[i+1][j+1] = Math.max(d[i+1][j+1],d[i][j]+triangle[i+1][j+1]);	
    		}
    	}
        
        //return Arrays.toString(d[length-1]); // 배열 값 확인
        return Arrays.stream(d[length-1]).max().getAsInt();
    }
}