알고리즘/프로그래머스
[프로그래머스] 네트워크 Java 풀이 및 해설
승민아
2024. 4. 6. 14:57
https://school.programmers.co.kr/learn/courses/30/lessons/43162
풀이 방법
프로그래머스 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;
}
}