3회차(01.11) - 결과

<프로그래머스 - 깊이/너비 우선 탐색(DFS/BFS)>

- Java

---

* 타겟넘버

class Solution {
    static int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers,target,0,0);
        return answer;
    }
    
    static void dfs(int[] numbers,int target, int cnt, int sum){
        if(cnt == numbers.length){
            if(sum==target){
                answer++;
            }
            return;
        }
        dfs(numbers,target,cnt+1,sum+numbers[cnt]);
        dfs(numbers,target,cnt+1,sum-numbers[cnt]);
    }
}

각 원소를 조합해서 더하고 뺀 값의 합이 target이 되는 횟수를 리턴하는 문제

 

cnt는 index의 역할을 하며 0부터 numbers.length-1 까지 증가

numbers.length가 되는 순간은 배열을 다 순회한 것이므로 종료되어야 한다.

이때 여태까지의 sum이 target 값과 같다면 answer를 증가시킨다.

dfs안에서 dfs를 호출하며 sum에 numbers[cnt]를 더하고 빼내가며 문제를 해결한다.

 

---

* 네트워크 

class Solution {
    static boolean[] check;
    public int solution(int n, int[][] computers) {
        int answer = 0;
        check = new boolean[n];
        for(int i=0; i<n; i++){
            if(check[i]==false){
                dfs(computers,i);
                answer++; 
            }
        }
        return answer;
    }
    static void dfs(int[][] computers,int i){
        check[i] = true; 
        for(int j = 0 ; j<computers.length; j++){
            if(i!=j && computers[i][j]==1 && check[j]==false){
                dfs(computers,j);
            }
        }
    }
}

네트워크의 개수를 구하는 문제 

 

연결되어 있는 애들 끼리 하나.

즉, 컴퓨터1, 컴퓨터2, 컴퓨터3 이 있는데,

컴퓨터1과 컴퓨터2가 연결되어 있고, 컴퓨터 3은 연결된 것이 없다면

네트워크는 두 개 인 것이다.

 

n은 컴퓨터의 갯수로 

boolean 배열을 활용해 각 컴퓨터를 검사했는지 check 한다.

따라서 크기는 n

 

반복문을 돌며

검사를 안한 경우에는 dfs를 통해 더 심층적으로 검사해준다.

이때 i를 넘겨주어 i컴퓨터에 대해 검사할 수 있도록 한다. (그니까 .. 음.. 인덱스 넘겨준다구요,, ㅎ ㅎ..)

이때 answer를 여기서 증가시켜준다. 이게 즉 네트워크의 갯수가 된다.

check가 true였다면 이미 검사가 끝난 것이기 때문이다.

만일 다음께 true면 그 이전 컴퓨터가 얘랑 어딘가 연결이 되어서 검사가 끝난 거겠쥬 ,,~?

또한 연결이 된건 네트워크의 개수로 노 인정이니까 ~

 

dfs를 통해서 심층적인 검사를 하게 된다.

우선 check[i] 를 true로 설정해 이 컴퓨터 check함! 을 표시

이때 이 컴퓨터를 i 컴퓨터라고 하겠다. i컴퓨터가 j 컴퓨터와 연결되어있는지 확인할 것이다.

문제의 제한사항에서 computers[i][i]는 항상 1이었다.

따라서 i는 j와 같지 않아야한다.

i!=j 이고 computers[i][j]가 1(연결)일때, 또한 check[j]가 false일때(j 컴퓨터 검사 x)

dfs를 호출하여 연결된 j컴퓨터를 검사한다.