알고리즘을 지난 5개월 동안 놓고있다가 최근 들어 다시 잡기 시작하면서 조금씩 예전의 감을 찾아가고 있는듯 하다.
네트워크
문제는 쉽게 말해 이어져 있는 노드들이 몇개가 있느냐를 묻는 문제이다
DFS, BFS 다양한 방법들이 있지만 접근하기 쉬운 BFS
를 통해 너비우선 탐색을 진행하였다
문제에서 요구사항 중 충족해야 하는 조건을 생각해보았다
1. 자기자신은 항상 연결되어있기에 항상 1, 즉 고려할 필요없음
2. 연결된 곳은 computers 배열의 인덱스로 접근하여 1인 곳을 파악
3. 그래프의 사이즈는 n*n 이기에 이를 고려하여 0 부터 n 까지 loop를 돌면서 탐색
4. 방문 여부는 따로 visited[]
배열을 두어 저장
static boolean[] visited; // 방문 여부를 저장
static int[][] graph; // 컴퓨터 그래프 저장
static int n; // 컴퓨터의 개수 저장
public static void bfs(int computer){
// 자기자신은 항상 연결 되어 있으니 고려하지 않음
Queue<Integer> queue = new LinkedList<>(); // 큐 생성
queue.add(computer); // 시작 위치 큐에 담기
visited[computer] = true; // 시작 위치 방문처리
while(!queue.isEmpty()){
// 큐가 비지 않을때 까지 계속
int node = queue.poll(); // 큐에서 하나의 노드를 빼옴
for (int i = 0; i < n; i++) {
if(i!=node && !visited[i] && graph[node][i]==1){
// 만약 노드가 자기자신이 아니고, 방문한 적이 없으며 연결되어있다면 방문처리 후 큐에 담아준다
queue.add(i);
visited[i] = true;
}
}
}
}
public static void main(String[] args) {
// 샘플 그래프
graph = new int[][]{{1, 1, 0}, {1, 1, 1}, {0, 1, 1}};
// 전역 변수 값 지정
n = graph.length;
visited = new boolean[n];
int cnt = 0;
for (int i = 0; i < n; i++) {
// 만약 해당 컴퓨터가 방문한적 없는 컴퓨터라면 bfs를 수행하고 카운트 1증가
if(!visited[i]){
cnt++;
bfs(i);
}
}
System.out.println(cnt);
}
import java.util.*;
class Solution {
static boolean[] visited;
static int[][] graph;
static int s;
public static void bfs(int computer){
Queue<Integer> queue = new LinkedList<>();
queue.add(computer);
visited[computer] = true;
while(!queue.isEmpty()){
int node = queue.poll();
for(int i=0; i<s; i++){
if(i!=node && !visited[i] && graph[node][i]==1){
queue.add(i);
visited[i] = true;
}
}
}
}
public int solution(int n, int[][] computers) {
visited = new boolean[n];
graph = computers;
s = n;
int answer = 0;
for(int i=0; i<n; i++){
if(!visited[i]){
answer++;
bfs(i);
}
}
return answer;
}
}