https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍
www.acmicpc.net
문제 분석
- 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수는 결국 1번과 연결
- 1번과 연결된 노드들을 모두 검사하여 count 하면 되겠구나?!
📝풀이방법
BFS 활용 ( Linkedlist, 2차원 배열)
사실 문제 자체는 간단해서
BFS 구현 연습 문제로 제격인 거 같습니다.
BFS의 경우 선입선출을 기본적인 구조로 가지고 있으며, 완전탐색에서 너비 우선 탐색의 의미로
DFS와 대비해 같은 범주(높이)에서 탐색할 때 유용한 방식입니다
풀이코드💻
import java.util.*;
public class BOJ_2606바이러스 {
static int cnt;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
boolean[] virus = new boolean[num +1];
LinkedList<Integer>[] adjList = new LinkedList[num +1]; //링크드 리스트
int N = sc.nextInt();
for(int i =0; i<=num ;i++)
adjList[i] = new LinkedList<Integer>(); //객체 생성
cnt= 0;
for(int i = 0; i< N; i++ ){
int v1 = sc.nextInt();
int v2 = sc.nextInt();
adjList[v1].add(v2);
adjList[v2].add(v1);
}
bfs_list(1,adjList,virus); //bfs 돌려보장
System.out.println(cnt);
}
public static void bfs_list(int v, LinkedList<Integer>[] adjList, boolean[] visited ){
Queue<Integer> queue = new LinkedList<Integer>();
visited[v] = true; //왔던 곳 체크!
queue.add(v);
while (!queue.isEmpty()){ //안에 하여튼 뭐가 있다는 거야~
v = queue.poll(); //하여튼 맨 마지막거 꺼내겠다는거야
Iterator<Integer> iter = adjList[v].listIterator(); //반복자 ( 밥먹자(X) ) 리스트 순회객체
while(iter.hasNext()){ //가지고 있어? 그럼 드가자!
int w = iter.next();
if(!visited[w]){ //방문 안했어?
visited[w] =true; //했따!
cnt++; //기념으로 cnt 한 번 찍자
queue.add(w); //이제 이동네 맛집 인거다!
}
}
}
}
}
'알고리즘 > 문제풀이' 카테고리의 다른 글
[백준_15683] 감시.java (0) | 2024.04.03 |
---|---|
[백준_14891] 톱니바퀴.java (0) | 2024.04.02 |
[백준_17136] 색종이 붙이기.java (0) | 2024.03.30 |
[소프티어] 나무 섭지 풀이에 관하여.java (0) | 2024.03.20 |
[9663_백준] N-Queen 문제풀이 (java) (0) | 2024.03.01 |