[Java] [매출하락최소화] 너비우선탐색(BFS)

Solution :

• 모든 노드는 팀장이 참여할때(bat) 참여하지않을때(bnat) 2가지 경우에 대한 값을 가진다.
• edges Arraylist의 모든 노드는 upside downside에 대한 2가지 정보를 필요로 한다.
• 말단 → 상위노드로 탐색이 필요하므로, 넓이우선탐색( Queue + indegree array )를 활용

중요 : 

• Class를 활용하여 새로운 Type의 구조체 만들기
• ArrayList를 활용하여 Link 정보 저장

 

프로그래머스 - 2021 KAKAO BLIND RECRUITMENT - 매출하락최소화

import java.awt.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.lang.Math;

class Solution {
    //value Class 만들기
    static class Value{
        int bat,bnat;
        Value(int bat, int bnat){
            this.bat = bat;
            this.bnat = bnat;
        }
    }
    
    static int N = 300001;
    static int[] indegree = new int[N];
    static Value[] value = new Value[N];
    static ArrayList<Integer> edges_up[] = new ArrayList[N];
    static ArrayList<Integer> edges_down[] = new ArrayList[N];
    static Queue<Integer> queue = new LinkedList();
    
    public int solution(int[] sales, int[][] links) {
        int answer = 0;
        //링크 UP/Down 방식으로 2개 생성
        for (int i=0; i<N; i++ ){
            edges_up[i] = new ArrayList<Integer>();
            edges_down[i] = new ArrayList<Integer>();
        }
        
        for (int i=0; i<N; i++ ){
            edges_up[i].clear();
            edges_down[i].clear();
            indegree[i]=0;
        }

        queue.clear();
        
        for(int i=0; i<links.length; i++){
            int s = links[i][0];
            int e = links[i][1];                      
            edges_up[e].add(s);
            edges_down[s].add(e);
            indegree[s]++;            
        }
        
        //초기화. 말단노드 초기값 설정 후 큐에 추가
        for(int i=1;i<=sales.length;i++){
            if(indegree[i]==0){
                queue.add(i);
                value[i] = new Value(sales[i-1],0);
            }
        }
        
        while(!queue.isEmpty()){          //큐가 없을때까지
            int chi = queue.poll();          //자신 노드
            if(chi==1) continue;              //자신 노드가 1일 경우에는 부모 노드가 없다. 계산필요없음
            int par= edges_up[chi].get(0);         // 부모노드 찾기
            indegree[par]--;                        // 부모노드 차수 0되면 다음 계산 가능
            if(indegree[par]==0){                   // 모든 자식노드가 업데이트 되었을때 계산
                queue.add(par);                      // 부모노드를 큐에 추가
                //bat = boss attendant
                int bat = sales[par-1]; 
                for(int i=0;i<edges_down[par].size();i++){
                    int tmp = edges_down[par].get(i);
                    bat += Math.min(value[tmp].bat, value[tmp].bnat);
                }                    
                //bnat  =  boss not attendant
                int bnat = Integer.MAX_VALUE;
                int tmp_sum = 0;
                for(Integer e : edges_down[par]){                    
                    tmp_sum += Math.min(value[e].bat, value[e].bnat);
                }
                
                for(Integer e : edges_down[par]){                      
                    if(tmp_sum - Math.min(value[e].bnat,value[e].bat) + value[e].bat < bnat){
                        bnat = tmp_sum - Math.min(value[e].bnat,value[e].bat) + value[e].bat;
                    }
                }
                value[par] = new Value(bat,bnat);
            }
        }
        
        answer = Math.min(value[1].bat,value[1].bnat);
        return answer;        
    }
}