백준 2606번 바이러스-JAVA

📝문제

📝알고리즘

//컴퓨터 수 N을 입력받고
//직접 연결된 컴퓨터 쌍의 수 connected 입력받고
//인접 리스트 adjList랑 방문 여부를 체크하는 visited 배열을 생성해서
//1번 컴퓨터부터 N번 컴퓨터까지 인접리스트를 초기화
//연결된 번호 쌍을 입력받으면
//방향이 정해져 있지 않으므로 양쪽에 추가
//dfs(1)의 반환값을 출력
//dfs 메서드는 다음과 같이 작성
//현재 컴퓨터 번호 start를 방문했다고 기록하고
//인접 리스트에 있는 수 중 방문하지 않은 요소를 찾으면
//count를 증가시키고 DFS를 호출
//더 이상 새로 방문할 직접 연결된 컴퓨터가 없으면
//count를 반환함

📝구현

import java.util.*;

public class Main{
    static ArrayList<Integer>[] adjList;
    static boolean[] visited;
    static int count=0;
    
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        int N=scanner.nextInt();
        int connected=scanner.nextInt();
        
        adjList=new ArrayList[N+1];
        visited=new boolean[N+1];
        
        for(int i=1;i<=N;i++){
            adjList[i]=new ArrayList<>();
        }
        for(int i=0; i<connected;i++){
            int a=scanner.nextInt();
            int b=scanner.nextInt();
            adjList[a].add(b);
            adjList[b].add(a);
        }
        System.out.print(dfs(1));
    }
    
    static int dfs(int start){
        visited[start]=true;
        for(int next: adjList[start]){
            if(!visited[next]){
                count++;
                dfs(next);              
            }
        }
        return count;
    }
}

📌기록하고 싶은 내용

일단 문제를 읽고 DFS가 먼저 떠올라서 DFS를 이용해서 풀었는데 지금 보니 BFS로도 풀 수 있을 것 같다.. 뭐가 더 효율적인지는 좀 더 알아봐야 할 것 같다..