문제 내용은 입력으로 간선을 받아 그래프를 구성한 뒤, 그래프가 총 몇개 나오는지를 반환해야 하는데 입력을 받아 코드를 짜다 보면 우측의 그림과 같은 구조가 나오게 되는데
이러한 그래프가 몇 개 있는지 반환하라는 얘기고, 입력으로 8 / 3 2 7 .. 이렇게 받은 것은 1 3, 2 2, 3 7 이렇게 그래프의 단선을 연결해 주면 된다는 얘기다
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.Map;
import java.util.Set;
public class Main {
public static void dfs(Map<Integer, ArrayList<Integer>> adjList, int node, Set<Integer> visited) {
visited.add(node);
for (int neighbor : adjList.get(node)) {
if (!visited.contains(neighbor)) {
dfs(adjList, neighbor, visited);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
for (int i = 0; i < count; i++) {
Set<Integer> visited = new HashSet<>();
int components = 0;
Map<Integer, ArrayList<Integer>> adjList = new HashMap<>();
int length = Integer.parseInt(br.readLine());
int[] edge = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int j = 0; j < length; j++) {
adjList.putIfAbsent(j + 1, new ArrayList<>());
adjList.putIfAbsent(edge[j], new ArrayList<>());
adjList.get(j + 1).add(edge[j]);
}
for (int node : adjList.keySet()) {
if (!visited.contains(node)) {
dfs(adjList, node, visited);
components++;
}
}
System.out.println(components);
}
}
}문제를 풀어보자면 일단 입력받은 내용을 그래프에 해당하는 adjList에 모두 넣어준 뒤, 방문한 적 없는 노드에만 dfs를 돌려주면서 visited 처리를 해 주면 그래프별 연결된 노드들은 모두 방문 처리가 되고
분리된 그래프만 하단의 for문에서 dfs를 시작하게 되므로, 해당 케이스만 더해준 뒤 출력해주면 입력받은 값으로 그래프가 몇개 생성되었는지 확인할 수 있다
Leave a Reply