[BaekJoon] 2606 바이러스 (java)
🔗 문제 링크
https://www.acmicpc.net/problem/2606
📝 문제 풀이 설명
이번 문제는 기본적인 BFS, DFS문제로 너비 또는 깊이 우선 탐색을 마친 뒤에 탐색을 하였던 node의 수를 return하면되는 문제였습니다.
👨🏻💻 작성한 코드
import java.io.*;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int computerNum = Integer.parseInt(br.readLine());
int connectNum = Integer.parseInt(br.readLine());
ArrayList<Node> nodeList = new ArrayList<>();
for (int i=1; i<=computerNum; i++) {
nodeList.add(new Node(i));
}
StringTokenizer st;
for (int i=0; i<connectNum; i++) {
st = new StringTokenizer(br.readLine());
int node1 = Integer.parseInt(st.nextToken());
int node2 = Integer.parseInt(st.nextToken());
nodeList.get(node1-1).edge.add(node2);
nodeList.get(node2-1).edge.add(node1);
}
System.out.println(bfs(nodeList, 1));
}
static int bfs(ArrayList<Node> grapgh, int start) {
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> set = new HashSet<>();
queue.add(start);
while(!queue.isEmpty()) {
int pop = queue.poll();
if (!set.contains(pop)) {
set.add(pop);
queue.addAll(grapgh.get(pop-1).edge);
}
}
return set.size()-1;
}
}
class Node {
int nodeId;
ArrayList<Integer> edge;
public Node(int nodeId) {
this.nodeId = nodeId;
edge = new ArrayList<>();
}
}
Author And Source
이 문제에 관하여([BaekJoon] 2606 바이러스 (java)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@seongwon97/BaekJoon-2606-바이러스-java저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)