Sangil's blog

왜? (문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/43162)

못 풀었을까?

1. DFS를 사용할 방법은 생각 했지만, 활용을 하지 못했다. 
-> 모든 노드에서 DFS 탐색을 하지 않아도 된다. 연결이 되어 있다면 연결된 노드는 패스하고 연결되지 않은 노드부터 탐색해야 하는데 해당 부분을 생각하지 못했다.

어떻게 풀면 될까?

1. STACK ( 1->2->3 )
2. STACK ( 1->2 )
3. STACK ( 1->2->4 )
4. STACK ( 1->2->4->7 )
5. STACK ( 1->2->4 )
6. STACK ( 1->2 )
7. STACK ( 1->2-> 5)
8. STACK ( 1->2 )
9. STACK ( 1-> 6 )
10. STACK ( 1 )
11. STACK () 
위의 노드를 다 순회하고 나면, 순회한 노드들은 다 연결 되어 있다는 것을 알 수 있다.
그러므로 해당 노드들은 다시 탐색할 필요가 없다. 이를 PATH[] 배열을 이용하여 연결되었음을 TRUE값으로 넣어주고, 해당 순회가 끝나면 PATH 배열에 연결되어 있지 않은 노드들부터 다시 순회하면 해당 문제를 풀 수 있다.

-JAVA 소스 : https://github.com/ChoiSangIl/algorithm/tree/master/BFS%2CDFS/progrmmers_C30_L43162_networks
DFS로 생각 할때는 STACK으로 생각하는게 쉬워서 STACK을 사용했지만, 구현은 재귀 함수로 구현했다. 처음엔 재귀함수로 짜는것도 이해가 안되었는데, 프로그래머스 연습문제 타겟넘버가 많은 도움이 됐다(https://programmers.co.kr/learn/courses/30/lessons/43165)

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