[백준] 2606: 바이러스 - BFS(너비우선탐색) + 유니온 파인드(UnionFind, Disjoint set) JAVA

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

2606번: 바이러스

풀이

이 문제는 전형적인 BFS 문제 혹은 유니온파인드 문제입니다.

우선 그래프를 구현하고, 시작점이 무조건 1로 고정되어있으므로 해당 1을 BFS(1) 시키면, 정답을 구할 수 있는 문제입니다.

코드

import java.util.*;


public class Main {
	public static int N,M;
	public static ArrayList<Node>[] nodes;
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	N = sc.nextInt();
    	M = sc.nextInt();
    	
    	nodes = new ArrayList[N+1];
    	for(int i=1;i<=N;i++) {
    		nodes[i] = new ArrayList<Node>();
    	}
    	
    	for(int i=0;i<M;i++) {
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		nodes[a].add(new Node(b));
    		nodes[b].add(new Node(a));
    	}
    	
    	//시작점은 1입니다.
    	BFS(1);
    	
    }
    
    public static void BFS(int start) {
    	Queue<Integer> queue = new LinkedList<>();
    	boolean[] visited = new boolean[N+1];
    	int cnt = 0;
    	visited[start] = true;
    	queue.offer(start);
    	
    	while(!queue.isEmpty()) {
    		int startNode = queue.poll();
    		for(int i=0;i<nodes[startNode].size();i++) {
    			int endNode = nodes[startNode].get(i).endNode;
    			if(visited[endNode] == false) {
        			queue.offer(endNode);
        			visited[endNode] = true;
        			cnt+=1;    				
    			}
    		}
    	}
    	System.out.println(cnt);
    }
    
}

class Node{
	int endNode;
	public Node(int endNode) {
		this.endNode = endNode;
	}
}

 

유니온 파인드로도 해결할 수 있습니다.

package Main;

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

public class Main {
    public static int N, M;
    public static int answer = 0;
    public static int[] arr;
    public static int[] parent;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		M = Integer.parseInt(st.nextToken());
		arr = new int[N];
		parent = new int[N+1];
		for(int i=0; i<=N; i++) {
			parent[i] = i;
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			unionParent(a, b);
		}
		
		for(int i=2; i<=N; i++) {
			findParent(i);
			if(parent[i] == 1) {
				answer += 1;
			}
		}
		System.out.println(answer);
	}
    
    public static int findParent(int x) {
    	if(x == parent[x]) return x;
    	return parent[x] = findParent(parent[x]);
    }
    
    public static void unionParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	if( a < b) {
    		parent[b] = a;
    	}
    	else if( a >= b){
    		parent[a] = b;
    	}
    }

}