그래프에 간선을 직접 넣지않고 [N+1][N+1] 그래프를 만들어 각 노드의 관계를 입력했다
for(int i=1; i<M+1; i++){
int r = sc.nextInt();
int c = sc.nextInt();
graph[r][c] = graph[c][r] = 1;
}
간선의 수만큼 그래프에 관계를 넣으면
0 1 2 3 4 5 6
1 0 1 0 0 1 0
2 1 0 0 0 1 0
3 0 0 0 1 0 0
4 0 0 1 0 0 1
5 1 1 0 0 0 0
6 0 0 1 0 0 0
모양의 그래프가 완성된다
main의 for문에서 방문하지 않은 노드를 넣으면
BFS에서 해당 노드의 연관 그래프를 찾는 for문을 실행한다
graph[temp][i] 가 -> 2 1 0 0 0 1 0 줄을 탐색하는것
첫번째 for문에서 1(시작)>2>5 를 탐색하고 res를 증가시키는것
두번째는 3(시작)>4>6 을 탐색후 res증가후 종료 (visited가 다 true)
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class B11724 {
static int N,M,res;
static int[][] graph;
static boolean[] visited;
static void bfs(int node){
Queue<Integer> queue = new LinkedList<>();
visited[node] = true;
queue.add(node);
while (!queue.isEmpty()){
int temp = queue.remove();
for(int i =1; i<N+1; i++){
if(!visited[i]&&graph[temp][i] ==1 ){
visited[i] = true;
queue.add(i);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
visited = new boolean[N+1];
graph = new int[N+1][N+1];
for(int i=1; i<M+1; i++){
int r = sc.nextInt();
int c = sc.nextInt();
graph[r][c] = graph[c][r] = 1;
}
res = 0;
for(int i=1; i<N+1; i++){
if(visited[i]) continue;
bfs(i);
res++;
}
System.out.println(res);
}
}
'연습문제 > JAVA' 카테고리의 다른 글
14503-로봇청소기 (0) | 2022.08.10 |
---|---|
7569-토마토 (0) | 2022.08.09 |
11724-연결 요소의 개수 (오답) (0) | 2022.08.09 |
2468-안전영역 (0) | 2022.08.08 |
2667-단지번호붙이기 (0) | 2022.08.08 |