[JS] - 이분탐색 알고리즘

이분탐색 알고리즘

• 매칭은 A 집단이 B 집단을 선택하는 방법에 대한 알고리즘
• 네트워크 알고리즘 연계되는 알고리즘 이분매칭 알고리즘

집단 A 와 집단 B 각사람이 원하는 항목이 있을경우 가장 효과적으로 매칭시킬수 있는 방법
=> 최대로 매칭 가장많이 연결되는 경우 찾는 문제

예제 문제

백준 - 소축사넣기

DFS알고리즘을 활용해 시간복잡도 O(V*E) n2

	let n = 3;
        let a = Array.from({length: n+1}, ()=> []);
        let d = Array.from({length: n+1}, ()=> 0);   //선택정보
        let c = Array.from({length: n+1}, ()=> false);  //방문정보    
        function DFS(x){
            //console.log("x:", x ,a[x].length);
            for(let i=0; i< a[x].length; i++){
                let t = a[x][i];
                //이미처리한 노드
                if(c[t]){ 
                    continue;
                } 
                c[t] = true;
                // 비어있거나 점유 노드에 다른 노드로 이동이 가능한지 확인
                if(d[t] === 0 || DFS(d[t])){
                    d[t] = x; 
                    return true;
                }
            }
            console.log(x , "실패");
            return false;
        }
        function solution(){   
            a[1].push(1);
            a[1].push(2);
            a[1].push(3);
            a[2].push(1);
            a[3].push(2);
            let count = 0;
            console.log("arr",  a , c);
            for(let i=1; i<=n; i++){ 
                c = Array.from({length: n+1}, ()=> false);  //방문정보 리셋
                //console.log(i);
                if(DFS(i)) count++;
            }
            console.log(`${count}` + "출력값");
            console.log(d);
            for(let i = 1; i< d.length; i++){
                if(d[i] != 0){
                    console.log(`${d[i]}`+ "->" + `${i}`);
                }
            }
            return 0;
        }
        solution();

출처 : https://blog.naver.com/ndb796/221240613074