[백준 / Java] 2606번 바이러스

사용한 알고리즘 (DFS)

DFS 

https://cobi-98.tistory.com/30

[필수 알고리즘] DFS 깊이 우선 탐색 (Stack 구조) 이해

 

 

🔒 2606번 바이러스

✔ 문제 설명

🚩 요구사항 분석

• 1번 컴퓨터가 웜 바이러스 - 시작 노드 1 고정

 

🔑 문제풀이

현재 정점을 1(1번 컴퓨터 웜 바이러스)로 시작하여

인접 정접이 더이상 없다면(4번 노드 같은 경우 해당 x) 해당 간선을 타고 돌아가 이를 반복하는 구조이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int vertex;
    public static int trunk;
    public static int[][] map;
    public static boolean[] visit;
    public static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        vertex = Integer.parseInt(br.readLine());
        trunk = Integer.parseInt(br.readLine());

        map = new int[vertex+1][vertex+1];
        visit = new boolean[vertex+1];

        for (int i = 0; i < trunk; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            map[a][b] = map[b][a] = 1;
        }
        dfs(1);
        System.out.println(count);
    }

    public static void dfs(int start){

        if(visit[start]) {
            return;
        }

        visit[start] = true;
        for (int i = start; i <= vertex; i++) {
            if (!visit[i] && map[start][i] == 1){
                count = count+1;
                dfs(i);
            }
        }
    }

}