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

코딩테스트 연습 - 네트워크 | 프로그래머스 (programmers.co.kr)

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

어떻게 생각하고 문제를 풀었는가?

연결된 네트워크의 수를 구하기 위해 DFS를 사용하였습니다.

0번 컴퓨터부터 네트워크에 연결되있지 않다면 새로운 네트워크에 추가하고, 연결 가능한 컴퓨터를 순회하면서 네트워크의 연결을 수행함으로서 네트워크의 수를 구할 수 있겠다고 생각하였습니다.

 

코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] computers) {
        int answer = 0;
        Stack<Integer> nodes = new Stack<>();
        boolean[] visited = new boolean[n];
        for(int i=0;i<n;i++){
            if(visited[i]) continue;
            answer++;
            nodes.push(i);   
            while(!nodes.empty()){
                int index = nodes.pop();
                visited[index] = true;
                for(int j=0;j<n;j++){
                    if(computers[index][j]>0 && !visited[j]) nodes.push(j);
                }
            }
        } 
        return answer;
    }
} 

테스트를 통과하는 코드를 작성하였습니다.

Stack을 활용하여 DFS를 구현하였으며 네트워크로 연결되지 않은 컴퓨터들을 네트워크로 만들어 DFS를 반복한 횟수를 반환하여 문제를 해결하였습니다.