프로그래머스 - 네트워크 - DFS(재귀, Stack)

1. 문제

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

2. 풀이

재귀를 Stack으로 생각하면 생각보다 간단하다. 재귀되는 것을 Stack에 넣는다고 생각하고 접근하면 꽤 쉽다.

3-1. 재귀 풀이

import java.util.*;

class Solution {
    boolean[] visit;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        visit = new boolean[n];
        
        for(int i = 0; i < n; i++){
            if(!visit[i]){
                answer++;
                visit[i] = true;
                dfs(i, computers);
            }
        }
        return answer;
    }
    
    public void dfs(int start, int[][] computers){
        for(int i = 0; i < computers[start].length; i++){
            if(computers[start][i] == 1){
                if(!visit[i]){
                    visit[i] = true;
                    dfs(i, computers);
                }
            }
        }
        return;
    }
}

3-2. Stack 풀이

import java.util.*;

class Solution {
    boolean[] visit;
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        
        visit = new boolean[n];
        
        for(int i = 0; i < n; i++){
            if(!visit[i]){
                visit[i] = true;
                answer++;
                
                Stack<Integer> stack = new Stack<>();
                
                stack.push(i);
                while(!stack.isEmpty()){
                    int network = stack.pop();
                    
                    for(int j = 0; j < computers[network].length; j++){
                        if(computers[network][j] == 1){
                            if(!visit[j]){
                                visit[j] = true;
                                stack.push(j);
                            }
                        }
                    }
                }
            }
        }
        return answer;
    }
}