네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.
컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.
제한사항
컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
각 컴퓨터는 0부터n-1인 정수로 표현합니다.
i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
computer[i][i]는 항상 1입니다.
입출력 예
입출력 예 설명
예제 #1 아래와 같이 2개의 네트워크가 있습니다.
예제 #2 아래와 같이 1개의 네트워크가 있습니다.
[간단설명]
BFS/DFS 탐색하면서, 네트워크 개수 구하는 문제
[접근방법]
1. 노드 리스트 구성
2. 부모 노드에 자식 리스트 넣기
3. BFS/DFS 정하기
4. 1번 탐색이 끝날 때마나 네트워크 개수 +1
[주의사항]
다른 BFS/DFS 문제는 1번 탐색하고 끝나지만,
이 문제는 탐색한 개수를 구해야하기 때문에
탐색이 끝나고 다시 탐색을 실행시키는 조건을 잘 정해야한다.
[소스공개]
import java.util.*;
class Solution {
// 노드 클래스
class Node{
int num; // 노드번호
List<Node> edge; //자식노드
boolean visited; //방문여부
// 생성자
Node(int num){
this.num=num;
this.edge = new LinkedList<>();
}
// 자식노드 추가
void add(Node node){
edge.add(node);
}
}
public int solution(int n, int[][] computers) {
int answer=0;
// 노드 리스트
List<Node> list = new ArrayList<>();
// 부모 노드 구성
for(int i=0;i<n;i++){
Node node = new Node(i);
list.add(node);
}
// 부모 노드에 자식 노드 추가
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j) continue;
if(computers[i][j]==0) continue;
list.get(i).add(list.get(j));
}
}
// DFS 탐색 스택
Stack<Node> stack = new Stack<>();
for(int i=0;i<n;i++){
if(list.get(i).visited) continue; // 방문한 노드면 PASS
list.get(i).visited = true; // 방문체크
stack.push(list.get(i)); // 스택에 노드넣기
// 위 노드에 연결된 네트워크를 전부 찾는다
while(!stack.isEmpty()){
Node now = stack.pop();
for(Node next : now.edge){
if(next.visited) continue; // 방문한 노드면 PASS
next.visited = true; // 방문체크
stack.push(next); // 스택에 노드넣기
}
}
// 네트워크 개수 증가
answer++;
}
return answer;
}
}
