문제 내용은 입력으로 그래프 간 간선을 받아서 그래프를 만들어준 후, ‘1번’ 컴퓨터가 바이러스에 걸렸을 경우 같은 그래프에 있는 노드의 갯수를 반환해줘야 하는데, 주의할 점은 1번 노드는 제외한 나머지 감염된 갯수를 가져와야 한다.
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;
public class Main {
static int ans = 0;
public static void dfs(Map<Integer, ArrayList<Integer>> adjList, int node,
HashSet<Integer> visited) {
visited.add(node);
for (int current : adjList.get(node)) {
if (!visited.contains(current)) {
ans++;
dfs(adjList, current, visited);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.readLine();
int count = Integer.parseInt(br.readLine());
Map<Integer, ArrayList<Integer>> adjList = new HashMap<>();
for (int i = 0; i < count; i++) {
int[] split = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
adjList.putIfAbsent(split[0], new ArrayList<>());
adjList.putIfAbsent(split[1], new ArrayList<>());
adjList.get(split[0]).add(split[1]);
adjList.get(split[1]).add(split[0]);
}
HashSet<Integer> visited = new HashSet<>();
if (adjList.size() > 0) {
dfs(adjList, 1, visited);
}
System.out.println(ans);
}
}문제를 풀어보자면 Map 안에 입력받은 내용들을 넣어 그래프 형태를 만들어준 뒤 dfs를 돌려줘야 하는데, 바이러스는 항상 1번 컴퓨터에만 걸리기 때문에 딱 한번만 돌려주면 나머지는 내부에서 계속 반복 호출해주고 끝나는 식으로 돌아가고 끝나게 된다.
dfs 메소드를 보면 일단 현재 node를 visited에 추가해준 후, 해당 노드에서 연결되는 값 차례로 꺼내주면서 다시 호출해서 visited 처리하는 식으로 진행되는데, 위 과정을 진행할 때마다 ans 값이 증가하므로 dfs가 모두 끝나고 나면, 1번 컴퓨터를 제외한 바이러스가 걸린 컴퓨터 갯수를 확인할 수 있다.
Leave a Reply