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

프로그래머스 <네트워크>

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

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

---

<네트워크>

n으로 컴퓨터의 수가 들어오고 computers라는 배열에 서로 연결된 노드의 정보가 들어온다.

computers는 2차원 int 배열로 computers[i][j]가 1이면 i와 j가 연결되어 있다는 의미이다.

 

answer은 연결된 컴퓨터들을 하나의 네트워크로 봤을 때, 몇 개의 네트워크가 존재하는지를 의미한다.

---

문제 해결

이 문제는 DFS/BFS를 사용해서 풀면 된다.

DFS를 사용하여 문제를 풀었다. visited 배열을 이용해 방문한 computer와 방문하지 않은 computer를 구분하였다.

0부터 n-1까지 for문을 돌려서 방문하지 않았으면 DFS를 호출했다. DFS가 호출된 횟수가 answer이 된다.

(연결된 computer들은 한 computer가 호출됬다면 모두 방문이 되기 때문에 DFS가 호출되지 않는다.)

 

DFS

자식 노드를 먼저 보며 탐색하는 알고리즘

stack을 이용한다.

stack의 top에 연결된 노드 중 방문하지 않은 노드를 넣고 방문처리 한다. stack이 빌 때까지 이를 반복한다.

---

코드

import java.util.Stack;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean[] visited = new boolean[n];
		for (int i = 0; i < n; i++) {
			visited[i] = false;
		}
		for (int i = 0; i < n; i++) {
			if(!visited[i]) {
				answer++;
				visited = dfs(n, computers, i, visited);
			}
		}
        return answer;
    }
    
    public static boolean[] dfs(int n, int[][] computers, int node, boolean[] visited){
        Stack<Integer> stack = new Stack<>();
        stack.push(node);
		visited[node] = true;
		while (!stack.isEmpty()) {
			int popN = stack.pop();
			for (int i = 0; i < n; i++) {
				if (computers[popN][i] == 1 && visited[i] == false) {
					visited[i] = true;
					stack.push(i);
				}
			}
		}
		return visited;
    }
}

---

결과

---