[Lv3, 60%, JS] 네트워크 / [Lv2, 60%, JS] 타겟 넘버

오늘처음해요·2024년 2월 3일

깊이/너비 우선 탐색(DFS/BFS) 네트워크

문제

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

내 답

function solution(n, computers) {
    const visited = Array(n).fill(false);
    let answer = 0;
    
    const dfs = (idx) => {
        visited[idx] = true;
        for(let i=0; i<n; i+=1) {
            if(!visited[i] && computers[idx][i]) dfs(i);
        }
    }
    
    computers.forEach((_,idx) => {
        if(!visited[idx]) {
            dfs(idx);
            answer +=1;
        }
    })
    
    return answer;
}

배운 점

DFS 코드를 보면 너무 짧아서 이해하기 쉬워보이지만

아무리 머릿속으로 작동 방식을 이해하려고 해도 많이 어려웠다

2시간 넘게 이해하지 못하고 문제를 못풀고 있어서

내가 진짜 바보인가 심각하게 고민을 했지만

결국엔 작동원리를 이해했다

DFS의 가장 중요한 포인트는

재귀이며, 방문 지점을 계속 체크해주면서

반복문을 탈출하는 게 포인트이다

깊이/너비 우선 탐색(DFS/BFS) - 타겟 넘버

문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

내 답

function solution(numbers, target) {
    let answer = 0;
    const len = numbers.length;
    
    const dfs = (count, sum) => {
        if(count === len) {
            if(sum === target) {
                answer += 1;
            }
            return
        }
        dfs(count+1, sum + numbers[count]);
        dfs(count+1, sum - numbers[count]);
        
    }
    
    dfs(0,0);
    
    return answer
}