[프로그래머스]DFS:네트워크(java)

문제보러가기

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

이문제는 전형적인 dfs라고 생각하고 풀었다. 딱 보자마자 탐색부터 해야지..라고 생각했는데 이게 그래프 노드의 숫자만 기억하면 되서 이차배열로 생각하다 복잡해졌었다. 쉬운문제이지만 기본기가 있어야 하는 문제라고 생각한다!

 

풀이방법

dfs로 탐색을 하면서 visited배열로 방문여부를 체크한다. 방문하지 않을경우 연결되지 않은 네트워크 이므로 따로 탐색을 한다.

 

package programers;

public class Network {

	static boolean[] visited;
	static int n;

	public static void main(String[] args) {

		n = 3;
		int[][] computers = { { 1, 1, 0 }, { 1, 1, 1 }, { 0, 1, 1 } };
		int answer=0;
		visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			if (visited[i] == false){
				dfs(i, computers);
				answer++;
			}
		}
		System.out.println(answer);
	}

	public static void dfs(int node, int[][] computers) {
		for(int i=0;i<n;i++){
			if(visited[i]==false && computers[node][i]==1){
				visited[i] = true;
				dfs(i,computers);
			}
		}
	}

}