[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 네트워크(43162)

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

코딩테스트 연습 - 네트워크 | 프로그래머스

public class Solution {

	public static void main(String[] args) {
//		int n =	3;	
//		int[][] computers = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
//		which returns 2
		
		int n =	3;	
		int[][] computers = {{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
//		which returns 1

		System.out.println(solution(n, computers));
	}
	
	static boolean[] visited;

	static int solution(int n, int[][] computers) {
        	visited = new boolean[n];
        
        	return dfsAll(computers);
        }
	
	static void dfs(int here, int[][] adjacentArray) {
		visited[here] = true;
		
		for (int i = 0; i < adjacentArray[here].length; i++) {
			if(adjacentArray[here][i] == 1 && !visited[i])
				dfs(i, adjacentArray);
		}
	}
	
	static int dfsAll(int[][] adjacentArray) {
		int count = 0;
		
		for (int i = 0; i < visited.length; i++) {
			if(!visited[i]) {
				dfs(i, adjacentArray);
				count++;
			}
		}
		
		return count;
	}
}

 0부터 n-1로 번호 붙여진 각각의 컴퓨터가 네트워크로 다른 컴퓨터들과 연결되어 있다. 다만, 연결되어 있지 않은 경우도 있다. 네트워크를 그래프의 컴포넌트, 컴퓨터를 정점, 연결을 간선으로 여기면, 문제에서는 정점의 개수와 인접 행렬이 주어지고, 이를 통해 그래프가 몇 개의 컴포넌트로 이루어져 있는지 구하는 것이다.

 dfs()를 통해 한 정점에서 간선으로 연결되어 있고 아직 방문하지 않은 정점들을 찾아 이동하며 방문 여부를 체크한다. 이렇게 순회된 정점들은 하나의 요소(컴포넌트)에 포함된 정점들이다. dfsAll()에서 dfs()를 호출한 횟수를 세어 여기서는 컴퓨터가 몇 개의 네트워크로 연결되어 있는지 구한다.