[DFS&BFS] 프로그래머스 알고리즘 Kit 문제풀이 (JS)

[Lv2] 타겟넘버

function solution(numbers, target) {
    var answer = 0;
    
    function dfs(idx,sum){
        if(idx<numbers.length){ 
           dfs(idx+1,sum+numbers[idx])  //+(left)
            dfs(idx+1,sum-numbers[idx]) //-(right)
        }
          else{ //leaf에 도달
           if(sum===target){ //target 찾음
                answer++;
            }   
          } 
        
    }
    
    dfs(0,0)
    return answer;
}

 

 

💡 DFS (preorder) 사용

 

모든 경우의 수를 구하고, target과 sum이 일치하는 경우를 count 하는 문제이다.

numbers의 숫자들을 순회하면서 +또는- 둘중의 경우로 가지치기를 진행하면서, 모든 경우의 수를 구한다.

leaf노드에 도달했을때, 해당 숫자의 연산결과와 target을 비교하면 되는데,

 

재귀함수에 들어가야할 매개변수는 idx와 sum이다.

depth가 증가할때마다 연산해야할 숫자가 바뀌기 때문에 idx와 sum 값을 계속 업데이트해줘야한다.

 

✅ +를 위한 dfs(idx+1,sum+numbers[idx])재귀가 반복되고, leaf 노드에 도달하면 else문의 작업을 마치고, -를 위한dfs(idx+1,sum-numbers[idx]) 재귀가 진행될것이다 → preOrder

 

[Lv2] 게임 맵 최단거리

function solution(maps) {
	
    //최종목적지 (n,m)
    let n = maps.length; // 맵의 세로 길이
    let m = maps[0].length; // 맵의 가로 길이
    let dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]; // 이동할 네 방향: 상하좌우

    function bfs() {
        let queue = [[0, 0, 1]]; // 시작 지점 (x, y) 및 이동 거리
        maps[0][0] = 0; // 시작점은 이미 방문한 상태로 표시
        
        while (queue.length > 0) {
            let [x, y, distance] = queue.shift(); // 현재 위치 및 이동 거리
            
            // 목표 지점에 도달한 경우
            if (x === n - 1 && y === m - 1) {
                return distance; // 현재까지의 이동 거리를 반환
            }
            
            // 상하좌우로 이동 시도
            for (const [dx, dy] of dir) {
                let newX = x + dx;
                let newY = y + dy;
                
                // 이동 가능한 위치이고, 방문하지 않은 경우
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && maps[newX][newY] === 1) {
                    queue.push([newX, newY, distance + 1]); // 큐에 추가
                    maps[newX][newY] = 0; // 방문한 위치는 0으로 변경하여 중복 방문 방지
                }
            }
        }
        
        // 모든 위치를 탐색한 후 목표 지점에 도달하지 못한 경우
        return -1;
    }

    return bfs();
}

가장 직관적이고 단순한 bfs풀이이다. 

한칸씩 이동할때마다 상하좌우 4가지 경우 중에서 순회하면서, 이동이 가능하면 해당 위치를 큐에 추가하고 이미 온길을 재방문 하지않기 위해 1이아닌 값을 넣어준다. 

 

✅ 이미 방문한 위치는 0으로 변경하여, 재방문을 방지해야 한다.

 

상하좌우 같은 여러가지 경우로 뻗어나갈 수 있는데, DFS처럼 끝까지 한놈만 팬다 느낌으로 한가지를 먼저 다 파고 재귀하는것이 아니라, 

BFS를 통해 한칸씩 이동하면서 각각의 경우를 번갈아가면서 이동한다.

 

 

✨ queue에서 현재위치를 shift하고 그 값을 기준으로 가능한 경로가지를 뻗어나가면서 queue에 push한다.

 

 

🔍 DFS보다 BFS가 적합한 경우

→ 최단경로 찾기는 BFS를 사용하면 시작 노드로부터 각 노드까지의 최단 경로를 찾을 수 있습니다. 반면, DFS는 가능한 한 깊게 노드를 탐색하기 때문에, 최단 경로를 보장하지 않는다!

 

 

 

 

[Lv3] 네트워크

function solution(n, computers) {
    const visited = Array.from({ length: n }, () => false);
    let answer = 0;

    function dfs(index) {
        visited[index] = true; // 현재 노드 방문했다고 표시

        for (let j = index+1; j < n; j++) { // 모든 노드 순회
            if (!visited[j] && computers[index][j]) { // 첫 방문이고 연결된 노드면
                dfs(j); // recursion
            }
        }
    }


    for (let i = 0; i < n; i++) {
        if (!visited[i]) { // 방문하지 않은 노드라면
            dfs(i); // DFS 수행하고
            answer++; // 카운트 증가
        }
    }
    
    return answer;
}

전형적인 그래프 문제로, 각 컴퓨터에서 출발해서, 그래프를 탐색하다가 더이상 연결된 컴퓨터가 없다면 하나의 네트워크를 발견한것이다.

 

✅ 한번 방문한 노드는 방문하지 않는게 이 문제의 포인트다. 무한루프에 빠질수 있으니 주의해야 한다!

✅ 무방향 그래프라고 가정하기 때문에, A에서 B의 연결이 있다면, B에서 A로반드시 연결 되어있다.

 

전체 배열을 순회하면서 방문하지 않으면, DFS 함수를 실행하는데, 첫방문&연결된 노드라면 재귀를 진행한다.

A가 B와 연결되어있다면, B로 파라미터로 변경해서 B와 연결된 컴퓨터를 찾는 느낌이다. 이렇게 이어서 재귀가 끝나고나면, 카운트를 증가시키는데 재귀가 끝난시점까지 모두 간접적으로 연결된 하나의 네트워크를 찾은것이라고 생각하면된다.

 

 

🔍 Refactor

class Queue {
    constructor() {
        this.items = {}; // 객체로 정의
        this.head = 0;
        this.tail = 0;
    }
    enqueue(item) {
        this.items[this.tail] = item;
        this.tail++;
    }
    dequeue() {
        const item = this.items[this.head];
        delete this.items[this.head];
        this.head++;
        return item;
    }
    
    size() {
        return this.tail - this.head;
    }
}

function solution(maps) {
    const queue = new Queue();
    const [n, m] = [maps.length, maps[0].length];
    const [targetX, targetY] = [n - 1, m - 1];
    
    const dx = [-1, 1, 0, 0]; // 좌, 우
    const dy = [0, 0, -1, 1]; // 상, 하
    
    queue.enqueue([0, 0, 1]); // 시작 위치와 거리
    
    while (queue.size() > 0) {
        const [x, y, distance] = queue.dequeue();
        
        // 상대방 진영 도착
        if (x === targetX && y === targetY) {
            return distance;
        }
        
        // 상하좌우 이동
        for (let i = 0; i < 4; i++) {
            const newX = x + dx[i];
            const newY = y + dy[i];
            
            // index 유효 범위 확인
            if (newX < 0 || newX >= n || newY < 0 || newY >= m) continue; // newY 범위 수정
            
            // 1 = 이동 가능
            if (maps[newX][newY] === 1) {
                queue.enqueue([newX, newY, distance + 1]);
                maps[newX][newY] = 0; // 재방문 방지
            }
        }
    }
    
    return -1; // 목표에 도달할 수 없는 경우
}

queue를 배열이 아닌 객체로 활용하면 shift를 통해 O(N)이였던 시간복잡도를 O(1)로 단축시킬 수 있다.

 

 

 

[Lv3] 단어 변환

function solution(begin, target, words) {
    let visited=[];
    let queue=[];
    let answer = 0;
    
    //early return
    if(!words.includes(target)) return 0; 
    
    queue.push([begin,answer]);
    
    while(queue.length>0){
        let [current,count]=queue.shift();
        
        
        if(current===target){ //변환완료
            return count; 
        }
        
        for(const word of words){
            //방문여부 확인
            if(visited.includes(word)) continue; 
            //한글자만 다른지 확인
            if(isOneDiff(current,word)){
                //queue에 push
                queue.push([word,++count]);
                //방문 남기기
                visited.push(word);
            }
        }
        
          
    }
    return answer;
 
}
    
 function isOneDiff(word1,word2){
        let differences=0;
        
        for(let i=0;i<word1.length;i++){
            if(word1[i]!==word2[i]) differences++;
        }
        return differences===1?true:false;
    }

모든경우의 수를 확인하지 않아도 target만 찾으면 되기때문에, BFS를 사용하였다.

 

✅ current=target에 도달하면 count를 리턴하는데, BFS는 가장 가까운 노드부터 차례대로 탐색하기 때문에 처음으로 target에 도달한 단계가 최소 변환 횟수이다