[프로그래머스] 네트워크

programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

문제 풀이 : 

처음에 사방 탐색으로 연결된 개수를 구하려고 해서 틀렸습니다.

1 0 1

0 1 0

1 0 1 

이러한 배열이 있을 때 사방 탐색으로 하면 답이 5지만 실제 답은 2입니다. 

 

그렇기 때문에 DFS를 활용하여 N크기의 visited 배열을 만들어 모든 행의 방문 처리를 확인하면서 답을 구합니다. 

방문하지 않은 배열을 DFS 로 들어가서

1. 방문처리를 해주고

2. 자기 자신을 제외한 연결된 네트워크면서, 방문하지 않은 곳을 다시 재귀적으로 들어갑니다.

재귀를 나오면 answer을 증가시켜서 답을 구해줍니다.

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