프로그래머스 - 네트워크

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 네트워크

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

풀이 1. (초급) - 재귀를 이용한 Bfs

class Solution {
    static boolean [] visited; 
    public int solution(int n, int[][] computers) {
        visited = new boolean [n];
		int answer = 0;
		for (int i = 0; i < computers.length; i++) {
			answer += dfs(computers,i);
		}
		return answer;
	}

	static int dfs(int[][] computers, int idx) {
		if(visited[idx]) return 0;
		visited[idx] = true;
		for (int i = 0; i < computers[0].length; i++) {
			if (i != idx && computers[idx][i] == 1) {
				dfs(computers,i);
			}
		}
		return 1;
	}
}

풀이 2. (초급) - Stack를 이용한 Bfs

import java.util.*;
class Solution { 
    public int solution(int n, int[][] computers) {
       boolean [] vst = new boolean [n];
		int cnt = 0;
		Stack <Integer> stack = new Stack<Integer>();
		for (int i = 0; i < vst.length; i++) {
			if(vst[i]) continue;
			
			cnt++;
			stack.add(i);
			while(!stack.empty()) {
				int  num = stack.pop();
				vst[num] = true;
				for (int j = 0; j < computers[num].length; j++) {
					if(computers[num][j] == 1 && !vst[j]) stack.add(j);
				}
			}
		}
		return cnt;
	}
}

// 데이터 크기가 작을 땐 stack이 빠르나 데이터의 크기가 클 땐 재귀가 더 빠르다.