코테 연습[자바 코테 준비 8일차] bfs 완탐(1)

목표 :  카카오 2022 블라인드 양궁 문제를 빠르게 풀자 

https://school.programmers.co.kr/learn/courses/30/lessons/92342

프로그래머스

 

문제는 간단하다,,, 하 ,, 항상 간단한데 

 

1. 문제를 잘 읽고 패턴을 찾는다.

2.코딩 ㄱ

 

주어진 배열을 이용하여 나올 수 있는 모두의 경우의수를 빠르게 구해야한다라고 느꼈다.

 

중복조합으로 접근시 비효율적인 풀이가 될것 같ㅏ..

 

// 프로그래머스의 환경에서는 단일 클라스 Solution 안에서  구현을 해야함으로  전역 변수 및 추가 함수 , 클라스의 구현시 static 을 선언해 주자.

 

import java.util.*;


class Solution {

    public static int max_diff = -1 ;


    public int[] solution(int n, int[] info) {
        // 어피치 n 발 이후 라이언 차례


        int[] answer = {max_diff};
        Test test  = new Test();

        return answer;
    }
    public static void dfs(int n , int depth, int start) {

    }
    public static class Test{

    }
}

 

프로그래머스 BFS/DFS 모음 이다.

 

https://school.programmers.co.kr/learn/courses/30/parts/12421

프로그래머스

 

 

 

완탐을 위한 bfs 예시이다.

static private boolean[] visit = new boolean[10];
public static void bfs(int start) {
    Queue<Integer> q = new LinkedList<>();
    q.offer(start);
    visit[start] = true;
    
    while(!q.isEmpty()){
        int tmp = q.poll(); 
        for(int i =0 ; i < n + 1 ; i++) {
            if(map[tmp][i] == 1 && visit[i] == false) {
                q.offer(i);
                visit[i] = true;
            }
        }
    }
    
}

 

 

 

자 문제를 풀자.

 

프로그래머스 타겟 넘버

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=java 

프로그래머스

 

문제를 분석하면

 

현 위치의 노드에의 값과 남은 자연수들의 합 또는 차를 구한 수가 목표 값보다 크다라는 논리에 둘다 참 또는 거짓을 제외하면 탐색이 가능하게 구성시 , 완전 탐색을 수행하지 않는다.

 

수도코드로 나타내면 

 

boolean case 1 =  [ curetnt Value + leftTotal > target  ]

boolean case2 = [curetnt Value - leftTotal > target ]

 

if(case1 == case2) : 탐색 x 

 

public boolean checkLeft(int depth, int[] numbers,int current,int target) {
    
    int leftTotal = 0;
    for(int i  = depth; i<numbers.length;i++) {
        leftTotal+=numbers[i];
    }
    
    boolean case1 =  current + leftTotal > target  ;
    boolean case2 =  current - leftTotal > target  ;

    if(case1 == case2) return false;
    
    return true;
}

 

제귀적인 접근

 

DFS

import java.util.* ;

class Solution {

    private static Map<String, Integer> memo = new HashMap<>();

    public int solution(int[] numbers, int target) {
        return countCombinations(numbers, target, 0, 0);
    }
    private static int countCombinations(int[] numbers, int target, int index, int sum) {
        String key = index + ":" + sum;

        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        if (index == numbers.length) {
            if (sum == target) {
                return 1;
            } else {
                return 0;
            }
        }

        int positive = countCombinations(numbers, target, index + 1, sum + numbers[index]);
        int negative = countCombinations(numbers, target, index + 1, sum - numbers[index]);

        int total = positive + negative;
        memo.put(key, total);

        return total;
    }

}

 

BFS 풀이 

public int countCombinations(int[] numbers, int target) {
    int count = 0 ;
    Queue<Pair> q = new LinkedList<>();
    q.offer(new Pair(0,0));
    while(!q.isEmpty()){
        Pair current = q.poll();
        int index = current.getIndex();
        int sum = current.getSum();
        if(index == numbers.length){
            if(sum == target){
                count++;
            }
            continue;
        }
        q.offer(new Pair(index +1 ,sum + numbers[index]));
        q.offer(new Pair(index +1 ,sum - numbers[index]));

    }
    return count;
}
private static class Pair {
    private int index;
    private int sum;

    public Pair(int index, int sum) {
        this.index = index;
        this.sum = sum;
    }

    public int getIndex() {
        return index;
    }

    public int getSum() {
        return sum;
    }
}