백준 2606 자바

 

백준 DFS, BFS 문제이고 풀이는 2개 다 가능합니다. 근데 저는 BFS 공부 중이라 BFS로 풀었습니다.

여기서 생각해야 할 점은 바이러스가 걸린 컴퓨터를 구하는 cnt를 언제 증가시켜줘야하냐? 입니다.

단순히 코드만 암기하면 안 되고 bfs 알고리즘에서 어느 부분이 감염되는 컴퓨터 역할을 하는지 생각해야 합니다.

 

문제의 그림 1을 보면, 1번이 걸리면 2,3이 걸리고 2번과 연결된 5번, 5번과 연결된 6번이 걸립니다.

즉, 2 3 5 6을 카운팅해서 4개가 나오는 겁니다.

자 그러면 이를 bfs 알고리즘에 접목시켜보면 1번과 연결된 2,3 컴퓨터를 발견할 때 count를 올려줘야 합니다.

마찬가지로 2번과 연결된 5번, 5번과 연결된 6번을 발견할 때도 count를 올려줘야 합니다.

 

import javax.naming.PartialResultException;
import java.util.*;
import java.io.*;
public class Main {

    static ArrayList<Integer>[] list;
    static int cnt = 0;
    static boolean[] visit;

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

        int N = Integer.parseInt(br.readLine());

        int pair = Integer.parseInt(br.readLine());

        visit = new boolean[N+1];
        list = new ArrayList[N+1];

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

        for (int i = 0; i < pair; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b =Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        BFS(1);

    }
    static void BFS (int R) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(R);
        visit[R] = true;

        while (!queue.isEmpty()) {
            int q = queue.poll();
            for (int i: list[q]) {
                if (!visit[i]) {
                    cnt++;
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
        System.out.println(cnt);
    }
}

 

시작은 언제나 1번 컴퓨터가 바이러스에 걸렸을 때니까 1번부터 시작입니다. 

아래에서 1을 넣었을 때를 보면

1. BFS(1) 호출 

2. queue에 1 넣고, visit[1] = true

3. while문 

q = 1, for (int i : list[1] )

list[1]은 2,5와 연결되어 있으므로 차례대로 visit[2] = true, visit[5] = true, cnt = 2

queue = 2,5 넣기

4. 2를 빼서 똑같이 하면 됩니다. 2와 연결된 3이 있으므로 visit[3] = true, cnt = 3

5. 5도 마찬가지입니다.

 

 

import java.util.*;
import java.io.*;
public class Main {

    static ArrayList<Integer>[] list;
    static int cnt = 0;
    static boolean[] visit;

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

        int N = Integer.parseInt(br.readLine());

        int pair = Integer.parseInt(br.readLine());

        visit = new boolean[N+1];
        list = new ArrayList[N+1];

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

        for (int i = 0; i < pair; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b =Integer.parseInt(st.nextToken());
            list[a].add(b);
            list[b].add(a);
        }
        BFS(1);

    }
    static void BFS (int R) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(R);
        visit[R] = true;

        while (!queue.isEmpty()) {
            int q = queue.poll();
            for (int i: list[q]) {
                if (!visit[i]) {
                    cnt++;
                    visit[i] = true;
                    queue.add(i);
                }
            }
        }
        System.out.println(cnt);
    }
}