알고리즘/프로그래머스

[프로그래머스] 네트워크 Java 풀이 및 해설

승민아 2024. 4. 6. 14:57

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

풀이 방법

프로그래머스 lv.3 단계 문제라 다들 DFS는 잘 알고 있을거라... 설명은 생략하고

간단히 처음 방문하는 노드라면 DFS를 통해 쭉 연결된 모든 노드를 방문하고 answer + 1을 해주면 된다.

 

전체 코드

import java.util.*;
class Solution {
    
    public void dfs(int[][] computers, boolean visit[], int idx) {
        Stack<Integer> s = new Stack<>();
        s.push(idx);
        
        while(!s.empty()) {
            int cur = s.peek();
            s.pop();
            
            for(int i=0; i<computers[cur].length; i++) {
                if(!visit[i] && computers[cur][i] == 1) {
                    visit[i] = true;
                    s.push(i);
                }
            }
        }
        
        
    }
    
    public int solution(int n, int[][] computers) {
        int answer = 0;
        boolean visit[] = new boolean[200];
        
        for(int i=0; i<n; i++) {
            if(!visit[i]) {
                answer++;
                visit[i] = true;
                dfs(computers, visit, i);
            }
        }
        return answer;
    }
}