백준 2606_바이러스_JAVA

https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

import java.util.*;
import java.io.*;

public class Main {
    static int N,M;
    static ArrayList<Integer>[] A;
    static boolean[] visited;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine()); // 컴퓨터 갯수
        M = Integer.parseInt(br.readLine()); // 컴퓨터의 연결선 갯수
        A = new ArrayList[N+1];
        visited = new boolean[N+1];

        // 2차원 배열로 생성
        for(int i=1; i<N+1; i++) {
            A[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            A[s].add(e);
            A[e].add(s);
        }
        DFS(1);

        System.out.println(count);
    }

    private static void DFS(int a) {
        visited[a] = true;
        for(int i:A[a]) {
            if(!visited[i]) {
                count++;
                DFS(i);
            }
        }
    }
}

 

2024 04 30 BFS로 다시 풀기

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static ArrayList<Integer>[] grid;
    static boolean[] visited;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine()); // 컴퓨터 갯수
        grid = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        for (int i = 1; i < n + 1; i++) {
            grid[i] = new ArrayList<>();
        }

        m = Integer.parseInt(br.readLine()); // 연결되어 있는 컴퓨터의 쌍 갯수

        for (int i = 0; i < m; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            // 양방향 그래프이기 때문
            grid[s].add(e);
            grid[e].add(s);
        }

        bfs(1);

        System.out.println(count);
    }

    public static void bfs(int s) {
        Queue<Integer> queue = new LinkedList<>();
        visited[s] = true;
        queue.add(s);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i : grid[cur]) {
                if (!visited[i]) {
                    queue.add(i);
                    visited[i] = true;
                    count++;
                }
            }
        }
    }
}

 

회고

- 간단한 DFS문제였다.

- 생각한대로 구현을 했는데 맞아서 기분이 좋다.