문제 내용은 정점과 간선 갯수를 받아 그래프를 형성한 후 연결 요소의 갯수를 세 줘야 하는데, 일단 개념을 정리부터 해 보자면 정점이 2개인데 간선이 0라면 1 / 2 따로 있는 경우니 2를 출력하고
정점이 2, 간선이 한개인데 1 – 2 이렇게 있다면 연결 요소는 한 개라고 볼 수 있다, 결국 그래프 내 분리되어 연결된 요소들이 총 몇 개가 있는지를 출력해줘야 하는데
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
public class Main {
static Set<Integer> visited = new HashSet<>();
static int count = 0;
static Map<Integer, ArrayList<Integer>> graph;
public static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited.add(start);
while (!queue.isEmpty()) {
Integer poll = queue.poll();
if (graph.get(poll) != null) {
for (int node : graph.get(poll)) {
if (!visited.contains(node)) {
queue.add(node);
visited.add(node);
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
graph = new HashMap<>();
for (int i = 0; i < split[1]; i++) {
int[] vertex = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
graph.putIfAbsent(vertex[0], new ArrayList<>());
graph.putIfAbsent(vertex[1], new ArrayList<>());
graph.get(vertex[0]).add(vertex[1]);
// 양방향(무방향)
graph.get(vertex[1]).add(vertex[0]);
}
for (int i = 1; i <= split[0]; i++) {
if (!visited.contains(i)) {
count++;
bfs(i);
}
}
System.out.println(count);
}
}문제 조건을 보면 간선 갯수가 십만 단위로 늘어나서 BFS로 푸는 것이 적절해 보이는데 Map 형태의 그래프에 간선 연결정보를 모두 넣어준 후, 정점 갯수만큼 for문을 돌려주면서
visited에 값이 없는 항목들만 bfs를 돌려주면 되는데, bfs로 들어와서는 Queue에 최초 값 넣고 빌때까지 돌려주되, 내용을 보면 그래프 안에 연결된 값들을 모두 큐에 넣으면서 visited 배열에 추가해주고 Queue를 계속 돌려주다 보면 한 번만 돌려도 연결된 모든 간선들을 확인할 수 있다
이런 식으로 정점별로 연결된 내용은 BFS로 모두 한 번에 제외되므로, 연결되지 않은 항목들만 돌려주다 보면 연결 요소의 갯수를 확인해서 출력해줄 수 있다
Leave a Reply