[Programmers - JAVA] 네트워크

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

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

 

 

문제

 

 

풀이

• 연결된 네트워크의 연결된 개수를 찾는 문제

 

 

과정

1.  연결된 경우를 확인하기 위한 boolean형 visited 생성.
2.  dfs 실행전 네트워크의 수 증가.
3.  모든 노드에 대해 dfs 실행. (단, 방문했던 경우는 제외. 연결된 곳 포함)
4.  노드 방문 표시.
5.  해당 노드에서 다른 노드로 연결된게 있는지 전체 탐색. 있는 경우 dfs 호출.

 

 

알고리즘 지식

• DFS(깊이 우선 탐색)

 

 

제출 JAVA 코드

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) {
					answer++;
					dfs(i, visited, computers);
				}
			}

			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);
				}
			}
		}
	}

 

 

 

Eclipse 컴파일용 JAVA

package DFS_BFS;

public class 네트워크 {

	public static void main(String[] args) {
		int[][] computers = { { 1, 1, 0 }, { 1, 1, 0 }, { 0, 0, 1 } };
		int n = 3;
		System.out.println(new Solution().solution(n, computers));
	}

	public static 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) {
					answer++;
					dfs(i, visited, computers);
				}
			}

			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);
				}
			}
		}
	}

}