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

문제 출처 - Programmers

문제는 여기

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

---

[풀이]

1. 방문 체크를 위해 visited 배열을 생성한다.

2. 방문하지 않은 곳일 경우에 dfs탐색을 한다.

3. dfs에서 방문을 하였다고 visited에 해당하는 곳을 true로 만들어준다.

4. 방문하지 않았고, 네트워크가 연결된 곳이라면 dfs탐색을 추가로 진행한다.

5. dfs 탐색이 끝나면 하나로 연결된 네트워크에 대한 탐색이 끝난 것이므로 결과를 1 증가시킨다.

6. 2~5번을 반복하고 모든 탐색이 끝나면 결과를 출력한다.

[접근]

1. DFS / BFS로 문제를 해결해야겠다고 생각하였고 해당 방법으로 문제를 해결하였다.

[코드]

public class Solution {
    public int solution(int n, int[][] computers) {
	    int answer = 0;
	    boolean[] visited = new boolean[n];

	    for (int i = 0; i < n; i++) {
            // 탐색하지 않은 것
		    if (visited[i] == false) {
			dfs(i, visited, computers);
			answer++;
		    }
	    }

	    return answer;
	}

	public void dfs(int node, boolean[] visited, int[][] computers) {
		visited[node] = true;

		for (int i = 0; i < computers.length; i++) {
            // 방문하지 않은곳이고 연결된 곳이라면
			if (visited[i] == false && computers[node][i] == 1) {
				dfs(i, visited, computers);
			}
		}
	}
}