알고리즘 스터디 7월 3주차 문제1 (바이러스)

Jul 13, 2020

Post Series

문제#

링크로 대체

풀이 및 주저리..

앞 문제에 이어서 BFS를 연습해보고자 풀어본 문제이다. 전에 풀었던 문제에서 BFS 부분만 따로 연습하는 느낌이였고 빠르고 깔끔하게 짜보자는 생각으로 하였다. 문제를 좀 더 꼼꼼하게 읽어서 자료구조나 다른 곳에서 막히지 않고 연습할 수 있었다. 컴퓨터의 바이러스 감염 여부를 갖고있는 boolean 배열을 만들어보고 (처음엔 네트워크인줄 알고 변수명을 저렇게 만들어버렸다.) 컴퓨터간의 연결 여부를 Hashmap 형태로 저장한다음 BFS 를 활용하여 하나씩 방문하면서 개수를 더해주었다.

코드

package baekjoon.algorithm.dfsbfs;

import java.util.*;

public class Problem2606 {
    static boolean[] isNetworkArr;
    static HashMap<Integer, ArrayList<Integer>> computerMap;
    static int answer = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();

        isNetworkArr = new boolean[n + 1];
        computerMap = new HashMap<>();

        for(int i = 0; i< m; i++){
            int start = sc.nextInt();
            int dest = sc.nextInt();
            sc.nextLine();

            if(!computerMap.containsKey(start)) computerMap.put(start,new ArrayList<>());
            if(!computerMap.containsKey(dest)) computerMap.put(dest,new ArrayList<>());

            computerMap.get(start).add(dest);
            computerMap.get(dest).add(start);
        }
        Queue<Integer> virusQue = new LinkedList<>();

        virusQue.add(1);
        isNetworkArr[1] = true;

        while(!virusQue.isEmpty()){
            int now = virusQue.poll();
            if(computerMap.containsKey(now)){
                for(int l : computerMap.get(now)){
                    if(isNetworkArr[l]) continue;
                    isNetworkArr[l] = true;
                    answer++;
                    virusQue.add(l);
                }
            }
        }

        System.out.println(answer);
    }
}

기억에 남길 것!

BFS의 Queue 사용