728x90
2023.07.05 - [Coding Test/programmers] - 네트워크 (BFS)
네트워크 (BFS)
def solution(n, computers): answer = 0 visited=[False]*n def BFS(v): queue=[] visited[v]=True queue.append(v) while queue: now=queue.pop(0) visited[now]=True for i in range(n): if i!=now and not visited[i] and computers[now][i]==1: queue.append(i) for x in
karla.tistory.com
import java.util.*;
class Solution {
public int solution(int n, int[][] computers) {
// DFS
boolean[] isVisited = new boolean[n];
int answer = 0;
for (int i=0; i<n; i++){
if(isVisited[i]) continue;
visitAll(i, computers, isVisited);
answer++;
}
return answer;
}
private void visitAll(int computer, int[][] computers, boolean[] isVisited){
Stack<Integer> stack = new Stack<>();
stack.push(computer);
while(!stack.isEmpty()){
int c = stack.pop();
if (isVisited[c]) continue;
isVisited[c]=true;
for (int next=0; next<computers[c].length; next++) {
if(computers[c][next]==0) continue;
stack.push(next);
}
}
}
}728x90