알고리즘 -3) DFS/ BFS

 

 

1. DFS(stack사용)

function dfs (graph, startNode){
    let visited = [];
    let stack = [start];

    while(stack.length!==0){
        let n = stack.pop();
        if (!visited.includes(n)){
            visited.push(n);
            let sub = graph[n].filter(x=>!visited.includes(x))
            for (let i of sub){
                stack.push(i);
            }
        }
    }
    return visited;
}

2. BFS(queue사용)

function bfs (graph, startNode){
    let queue = [];
    let visited = [];
    queue.push(startNode);

    while(queue.length!==0){
        let now = queue.shift();
        if(!visited.includes(now)){
            visited.push(now);
            let sub = graph[n].filter(x=>!visited.includes(x));
            for (let i of sub){
                queue.push(i);
            }
        }
    }
    return visited;
}

 

 

 

3.최단경로

let queue = [start];
let visited = [start];

function solution (){
    let count = -1;

    while(queue.length!==0){
        count += 1;

        let size = queue.length;

        for(let i = 0;i<size; i++){
            let node = queue.splice(0,1);
            if(node == end){
                return count;
            }
            for (let nextNode in graph[node]){
                if(!visited.includes(graph[node][nextNode])){
                    visited.push(graph[node][nextNode]);
                    queue.push(graph[node][nextNode]);
                }
            }
        }
    }
}

 

 

4. 최장경로

const graph = {1: [2, 3, 4],
    2: [1, 3, 4, 5, 6],
    3: [1, 2, 7],
    4: [1, 2, 5, 6],
    5: [2, 4, 6, 7],
    6: [2, 4, 5, 7],
    7: [3, 5, 6]};

const user_input = prompt('입력해주세요').split(' ');
const start = parseInt(user_input[0], 10);
const end = parseInt(user_input[1], 10);

let queue = [start];
let visited = [];

function solution(n, visited){
    let node = n[n.length-1];
    let length = 0;

    if ( node ==end){
        return visited.length;
    }
    if(visited.includes(node)){
        return visited.length;
    }else{
        visited.push(node);
    }
    let max = [];

    for (let next_node in graph[node]){
        n.push(graph[node][next_node]);

        max.push(length, sol(n, visited));
        length = Math.max.apply(null, max);

        queue.pop();
    }
    return length;
}

console.log(sol(queue, visited))

 

 

5. 가장 긴 공통 수열 부분 구하기

 

let input = [] 
require('readline') .createInterface(process.stdin, process.stdout) 
    .on('line', function(line) { 
        input.push(line.trim()) 
    }) 
    .on('close', function() { 
        const str1 = input[0].split('') 
        const str2 = input[1].split('')

        function lcs(str1, str2){
            const array = Array.from(Array(2000), ()=>Array());
            for (let i = 0; i<=str1.length; i++){
                for (let j = 0; j<= str2.length; j++){
                    array[i][j] =0;
                }
            }
        
            for (let i = 1; i<=str1.length; i++){
                for(let j =1; j<=str2.length; j++){
                    if (str1[i-1]===str2[j-1]){
                        array[i][j] = dp[i-1][j-1]+1;
                    }else{
                        array[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                    }
                }
            }
            return array[str1.length][str2.length];
        }


console.log(lcs(str1, str2));
});

// 답안
// function sol(string){
//     let result = [];
//     for (let i=1; i<string.length+1; i++){
//         for (let j=0; j<i; j++){
//             result.push(string.slice(j, j+string.length-i+1));
//         }  
//     }
//     return result;
// }
    
// const inputOne = prompt('첫번째 문자열을 입력해주세요.');
// const inputTwo = prompt('두번째 문자열을 입력해주세요.');
// const arrayOne = sol(inputOne);
// const arrayTwo = sol(inputTwo);

// //공통 부분 문자열 찾기- 교집합
// let intersection = arrayOne.filter(x => arrayTwo.includes(x));

// //문자열 길이로 내림차순 정렬
// intersection.sort((a,b)=>{
//     return b.length-a.length;
// });

// console.log(intersection[0].length);

 

 

 

6. 조합(순서 관계 없이 만들기)

function combination(chars){
    let combi = [];

    const f = (prefix, chars)=>{
        for( let i = 0; i<chars.length; i++){
            combi.push(prefix + chars[i]);
            f(prefix + chars[i], chars.slice(i+1));
        }
    }
    f('', chars);

    const result = combi.filter(x =>x.length ===n);
    console.log(result);

    return result.length;

}

const arr = prompt('입력해주세요').split(',');
const n = parseInt(prompt('조합의 수를 입력해주세요'), 10);

console.log(combination(arr));

arr : [1,2,3,4] 배열 
num: 3 4개 중 3개를 뽑음
function combination(arr, num) {
  let result = [];
  if(num == 1) return arr.map(e => [e]);
  
  arr.forEach((e,i,array) => {
    let rest = array.slice(i+1);
    let combinations = combination(rest,num-1);
    let combiArr = combinations.map(x => [e, ...x])
    result.push(...combiArr);
  }) 
  return result;
}

 

7. 순열(순서 관련해서 만들기)

function solution(chars){
    let permute = [];
    const f = (prefix, chars)=>{
        for(let i = 0; i<chars.length; i++){
            permute.push(prefix + chars[i]);
            if(permute.indexOf(chars[i]+prefix)===-1){
                permute.push(chars[i]+prefix);
            }
            f(prefix + chars[i], chars.slice(i+1));
        }
    }
    f('', chars);

    let result = permute.filter(x=>x.length===len);
    result.sort((a,b)=> {return b-a});
    return result[0];
}

const num = prompt('숫자를 입력하세요').split('');
const len = parseInt(prompt('몇 개의 수를 선택하시겠습니까?'),10);
console.log(solution(num));

function combination(arr, num) {
  let result = [];
  if(num == 1) return arr.map(e => [e]);
  
  arr.forEach((e,i,array) => {
    let rest = [...array.slice(0,i), ...array.slice(i+1)];
    let combinations = combination(rest,num-1);
    let combiArr = combinations.map(x => [e, ...x])
    result.push(...combiArr);
  }) 
  return result;
}

function findPrimeNumbers(numberList, prevNumber) {
  const frontPaddingNumber = prevNumber || '';

  return numberList.reduce((primeNumbers, number, index) => {
    if (isPrimeNumber(Number(frontPaddingNumber + number))) {
      primeNumbers.push(Number(frontPaddingNumber + number));
    }

    const nextNumberList = [...numberList];
    nextNumberList.splice(index, 1);

    const result = findPrimeNumbers(
      nextNumberList,
      frontPaddingNumber + number,
    );
    primeNumbers.push(...result);

    return primeNumbers;
  }, []);
}

나중에 new Set(배열)의 형식으로 해줘야 중복이 제거된다.