[BOJ] 2606. 바이러스

유니온파인드 내지는 DFS를 이용하여 1과 연결된 것을 찾는 문제이다.

첫번째로 유니온파인드로 구현해보았다. 이문제에서 유니온파인드를 사용하면서 두가지 주의할점을 찾았다. 첫째, 경로의 최적화를 하기위해 find함수에서 return find(p[num]);대신 return p[num]=find(p[num]);을 사용해주었다. 둘째로 마지막에 모든 정점에 대하여 find함수를 한번씩 실행시켜줘서 부모를 저장하고있는 p배열을 갱신해주는 작업을 하였다. 이 작업은 필수적으로 해야하는 작업인데 놓치기 쉬움으로 항상 습관적으로 해야한다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_2606_바이러스 {
    
    static int N;
    static int[] p;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        p=new int[N+1];
        for(int i=1;i<=N;i++)
            p[i]=i;
    
        int M=Integer.parseInt(br.readLine());
        
        for(int i=0;i<M;i++) {
            st=new StringTokenizer(br.readLine());
            int num1=Integer.parseInt(st.nextToken());
            int num2=Integer.parseInt(st.nextToken());
            union(num1, num2);
        }
        
        for(int i=1;i<=N;i++)        //p값 갱신
            find(i);
        
        int count=0;
        for(int i=2;i<=N;i++) {
            if(p[i]==p[1])        //또는 find(i) == find(1)로 비교
                count+=1;
        }
        
        System.out.println(count);
    }
    
    static int find(int num) {
        if(p[num]==num)
            return num;
        
        return p[num]=find(p[num]);
    }
    
    
    static void union(int num1,int num2) {
        num1=find(num1);
        num2=find(num2);
        
        if(num1<num2)    
            p[num2]=num1;    //작은수를 할당
        else
            p[num1]=num2;
    }
    
}
 

 

다음으로는 일반적인 DFS를 이용하여 구현해보았다.

package boj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main_bj_2606_바이러스_2 {
    
    static int N;
    
    static List<Integer>[] list;
    static boolean[] visit;
    
    static int count;
    
 
    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        N=Integer.parseInt(br.readLine());
        list=new ArrayList[N+1];
        for(int i=0;i<=N;i++)
            list[i]=new ArrayList<>();
        
        visit=new boolean[N+1];
        
        int M=Integer.parseInt(br.readLine());
        
        for(int i=0;i<M;i++) {
            st=new StringTokenizer(br.readLine());
            int num1=Integer.parseInt(st.nextToken());
            int num2=Integer.parseInt(st.nextToken());
            list[num1].add(num2);
            list[num2].add(num1);
        }
        
        dfs(1);
        System.out.println(count-1);
    }
    
    static void dfs(int cur) {
        count+=1;
        visit[cur]=true;
        
        for(int next:list[cur]) {
            if(visit[next]==false) {
                dfs(next);
            }
        }
    }
}