on
[백준알고리즘-JAVA]2606번 풀이(바이러스) - 초보도 이해하는 풀이
[백준알고리즘-JAVA]2606번 풀이(바이러스) - 초보도 이해하는 풀이
안녕하세요
인포돈 입니다.
백준 알고리즘 2606번 풀이입니다.
* 참고사항
- 개발환경은 eclipse을 기준으로 작성되었습니다.
- java언어를 이용하여 문제를 풀이합니다.
- 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
- 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.
백준 2606 (바이러스)
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 11번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
입력, 출력 예제
성공 코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static boolean[] check; static int[][] arr; static int count = 0; static int node, line; static Queue q = new LinkedList<>(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); node = Integer.parseInt(br.readLine()); line = Integer.parseInt(br.readLine()); arr = new int[node+1][node+1]; check = new boolean[node+1]; for(int i = 0 ; i < line ; i ++) { StringTokenizer str = new StringTokenizer(br.readLine()); int a = Integer.parseInt(str.nextToken()); int b = Integer.parseInt(str.nextToken()); arr[a][b] = arr[b][a] = 1; } dfs(1); System.out.println(count-1); } public static void dfs(int start) { check[start] = true; count++; for(int i = 0 ; i <= node ; i++) { if(arr[start][i] == 1 && !check[i]) dfs(i); } } }
바이러스 알고리즘은 쉽게 해결할 수 있었습니다. 앞서 BFS와 DFS를 풀어보셨다면, 해당 코드를 약간만 변형한다면 쉽게 풀리기 때문이죠. 즉, 기본적인 DFS, BFS의 기본적인 활용 문제라고 보시면 됩니다.
STEP을 따라가며 쉽게 이해해보도록 하죠
알고리즘 흐름도
입력 받기 -> 인접 행렬에 값 넣어주기 -> DFS 실행하기 -> 출력하기
STEP1 입력 받기 및 인접 행렬 값 넣어주기
node = Integer.parseInt(br.readLine()); line = Integer.parseInt(br.readLine()); arr = new int[node+1][node+1]; check = new boolean[node+1]; for(int i = 0 ; i < line ; i ++) { StringTokenizer str = new StringTokenizer(br.readLine()); int a = Integer.parseInt(str.nextToken()); int b = Integer.parseInt(str.nextToken()); arr[a][b] = arr[b][a] = 1; }
뭐 별거 없습니다. 처음에 NODE의 개수
두 번째 입력은 line 즉 간선의 개수
세 번째부터는 연결된 노드의 쌍을 입력받습니다.
받은 값은 arr[a][b] = a [b][a] = 1의 값을 넣어줍니다. 양쪽에 다 넣어주는 이유는 1, 2나 2,1이나 같은 의미이기 때문이죠
arr [][] 은 인접 행렬을 표현하기 위한 배열
check []은 이미 바이러스에 감염되었는지를 판단하는 배열의 역할을 수행합니다
STEP2 DFS 구현하기
public static void dfs(int start) { check[start] = true; count++; for(int i = 0 ; i <= node ; i++) { if(arr[start][i] == 1 && !check[i]) dfs(i); } }
사실 이번 문제는 DFS든 BFS든 어떠한 방법으로도 구할 수 있습니다.
DFS의 경우 별거 없습니다. 처음 값으로는 1을 줍니다.
바이러스에 감염되었으니 1을 COUNT 해줍니다.
자 그다음 FOR문을 돌립니다.
만약 인접 행렬의 시작 노드와 연결된 값이 1이라면 확인합니다 CHECK로 이미 감연 된 노드인지
만약에 둘 다 맞다면, DFS를 해당 노드로 다시 실행합니다.
그렇게 된다면 다음은 1번 노드와 연결된 다음 노드의 CHECK에 TRUE가 입력되고 또 COUNT가 세어집니다.
이러한 식으로 DFS가 구현됩니다.
물론 처음 DFS를 접해보시면 구하기 힘들겠지만, 많이 풀어봐야 합니다!
from http://infodon.tistory.com/97 by ccl(A) rewrite - 2021-09-28 11:26:31