Algorithm/BaekJoon
2606번 : 바이러스
히욤이
2019. 3. 7. 00:50
2606번 : 바이러스
* 문제 출처 : 백준 알고리즘
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main_2606 { static int[][]map; static boolean[] visit; static int com; static int cnt; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); com = Integer.parseInt(br.readLine()); //컴퓨터 수 int con = Integer.parseInt(br.readLine()); //연결되어 있는 컴퓨터 쌍의 수 map = new int[com+1][com+1]; //좌표 visit = new boolean[com+1]; //방문 여부 StringTokenizer st; for (int i = 0; i < con; i++) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()); int y = Integer.parseInt(st.nextToken()); map[x][y] = map[y][x] =1; //서로 연결 } cnt = 0; //바이러스 횟수 dfs(1); //1번부터 시작 System.out.println(cnt); } static void dfs(int depth) { //현재 컴퓨터 번호 if (visit[depth]) { //현재 컴퓨터 번호를 방문 했으면 돌아감 return; } if (depth >com) { //컴퓨터 번호가 컴퓨터의 수를 증가하면 돌아감 return; } //현재 컴퓨터 번호를 방문하지 않았다면 visit[depth] = true; //방문 체크 for (int i = 1; i <= com; i++) { if (!visit[i] && map[i][depth]==1) { //방문하지 않았고 현재 컴퓨터 번호와 연결되어 있는 경우 cnt++; //감염 횟수를 1증가 dfs(i); //i번째 컴퓨터 dfs } } } } | cs |