[BFS,DFS]

BFS

1.동작원리 = 큐

2.구현 방법= 큐 자료구조(선입선출FIFO구조) push와 shift를 사용해 자료구조를 구현한다.

3.최소값을 구하는 문제이기때문에 bfs가 더빠르다.

 

function solution(begin, target, words) {
    const visited = []
    const queue = []

    // 변환할 수 없는 경우
    if (!words.includes(target)) return 0 //words안에 타겟이 없을때 0을 반환한다.//2번째 테스트 케이스 통과
   //첫번째 테스트 케이스 통과하기위해 bfs를 사용하자
    queue.push([begin, 0])//큐 시작

    while(queue) {//큐를 이용해 반복문사용
        const [currentNode, count] = queue.shift()//큐에서 하나의 원소를 뽑아 출력 구조..분해...할당!
        visited.push(currentNode)//반복문을 돌때마다 방문한 노드를 visited에 넣어준다.
            console.log(currentNode) 
        if (currentNode === target) {//큐에서 뽑은 단어가 타겟에 있다면 카운트를 출력한다.
            
            return count
        }

        words.forEach((changeWord) => {//words의 각각의 요소에대하여 반복문을 돌려 diff를 0으로 정의해 바꼈는지 체크해준다.
            let diff = 0

            if (visited.includes(changeWord)) return // 만약 내가 넣은 현재노드에 바뀐 단어가 없다면 아래반복문 실행
   
            for (let i = 0; i < currentNode.length; i++) {
                if (currentNode[i] !== changeWord[i]) diff++
            
               
            }

            if (diff === 1) {
           
                queue.push([changeWord, count + 1])
            }
        })
        
    }
}

프로그래머스 단어변환 문제

 

DFS

1.스택(선입후출구조 or 후입선출구조  )

2.stack을 정의하고 push와 pop을 사용해 스택 자료구조를 구현하거나 재귀함수(자기자신을 호출하는 함수)를 이용한다

3.최대값을 구하는문제

function solution(tickets){
    let answer = [];  //가능한 루트들을 담을 배열

    function dfs (extra, cur,route ) {
    //3가지 인자를 받는다. 남은 티켓, 현재 위치, 배열
         if(extra.length===0){
         //extra의 길이가 0이라는 것은 tickets에 있는 티켓을 모두 사용했다는것.
         //그렇지 않을 경우엔 길이가 0이 될 수 없다.
             answer.push(route)
             //모두 사용했으니 route를 answer에 푸쉬해주자. 
         }
         else{
         //길이가 0이 아니라면 아직 티켓이 남았다는 얘기
             extra.forEach(([departure, destination], idx) => {
             //forEach문으로 구조분해할당으로 하나의 배열마다 접근하고, 인덱스 가져온다.
                if( cur === departure){
                // 항상 출발지는 같아야한다
                     const newTickets = [...extra]; //티켓을  복사
                     newTickets.splice(idx,1)   
                     //cur과같은 출발지가 있는 배열을 빼준 배열을 만든다.

                     dfs(newTickets, destination, route.concat(destination))
                  //하나가 빠진 배열과 데스티네이션, 도착지를 추가한 배열을 재귀돌린다.
                  //한바퀴를 돈 상태에선 다음과 같을거다.
                 }
             });
         }
     }
     dfs(tickets , "ICN" , ["ICN"])
     //초기값을 설정한다. 인천에서 출발하여야하니 현재위치에 인천을,
     //배열안에도 인천을 넣어준 상태로 출발
     return answer.sort()[0];
     //오름차순 정렬해서 첫번째 요소만 꺼낸다.
 }

 

프로그래머스 여행경로 문제를 통해 dfs를 구현해보았다.