[JAVA] 알고리즘 고득점 kit dfs/bfs

 

 

타겟 넘버

 

가장 기본적인 dfs bfs

 

기본 dfs

import java.util.*;

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
        
        dfs(numbers, target, 0, 0);
        
        return answer;
    }
    
    private void dfs(int[]numbers, int target, int index, int sum){
        
        if(index == numbers.length){
            
            if(target == sum){
                answer++;
            }
            
            return;
        }
             
        dfs(numbers, target, index+1, sum + numbers[index]);
        dfs(numbers, target, index+1, sum - numbers[index]);
        
    }
    
    
}

 

 

 

 

dfs를 클래스 변수 안쓰고

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(numbers, target, 0, 0);
    }
    
    private int dfs(int[] numbers, int target, int index, int sum) {
        if(numbers.length == index){
            if(target == sum){
                return 1;
            }
            return 0;
        }
        
        return dfs(numbers, target, index + 1, sum + numbers[index]) + 
            dfs(numbers, target, index + 1, sum - numbers[index]);
    }
    
}

 

파이썬때 그대로 풀었는데 이렇게 풀면 메모이제이션이 가능하다는 장점이 있다

dfs 파람에 따라 리턴 값이 정해져 있기 때문

 

여기서는 index, sum이 같은 경우라면 return 값이 같을 것이다

이럴땐 클래스 변수로 hashmap 선언해서 key, value로 저장해놓기

 

 

 

 

 

게임맵 최단거리

 

기본 그래프 bfs

import java.util.*;

class Solution {
    public int solution(int[][] maps) {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        
        int answer = 0;
        
        int n = maps.length;
        int m = maps[0].length;
        
        Queue<int[]> q = new ArrayDeque<>();
        boolean [][] visited = new boolean[n][m];
        
        q.add(new int[] {0, 0, 1});
        visited[0][0] = true;
        
        
        while(!q.isEmpty()) {
            int[] polled = q.poll();
            int x = polled[0];
            int y = polled[1];
            int move = polled[2];
            
            if(x==n-1 && y==m-1) {
                return move;
            }
            
            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(0 <= nx && nx < n && 0<= ny && ny < m) {
                    if(maps[nx][ny] == 1 && visited[nx][ny] == false ) {
                        q.add(new int[] {nx, ny, move+1});
                        visited[nx][ny] = true;
                    }
                }
                
            }
            
            
        }
        
        return -1;
    }
}