<백준> 2606번 자바 알고리즘[BFS]

2022 / 1 월 풀이 

import java.util.*;

public class Main
{   
    
    static int cnt;
    
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int m = in.nextInt();
		int n = in.nextInt();
		cnt = 0;
		
		LinkedList<Integer>[] adjList = new LinkedList[m + 1];
		boolean[] visited = new boolean[m + 1];
		
		for(int i = 1; i <= m; i++){
		    adjList[i] = new LinkedList<>();
		}
		
		for(int i = 0; i < n; i++){
		    int a = in.nextInt();
		    int b = in.nextInt();
		    
		    adjList[a].add(b);
		    adjList[b].add(a);
		    
		}
		
		for(int i = 1; i <= m; i++){
		    Collections.sort(adjList[i]);
		}
		
		BFS(1, adjList, visited);
		System.out.println(cnt);
		
	}
	
	private static void BFS(int v, LinkedList<Integer>[] adjList, boolean[] visited){
	    Queue<Integer> queue = new LinkedList<Integer>();
	    visited[v] = true;
	    queue.add(v);
	    
	    while(queue.size() != 0){
	        v = queue.poll();
	        
	        Iterator<Integer> iter = adjList[v].listIterator();
	        while(iter.hasNext()){
	            
	            int w = iter.next();
	            if(!visited[w]) {
	                visited[w] = true;
	                queue.add(w);
	                cnt++;
	            }
	        }
	        
	    }
	}
}

2022 / 10 / 06 

dfs 재귀로 풀어봤다 

 

import java.util.*;

public class Main
{   
    static final int MAX_N = 1000;
    static int N, E;
    static boolean[] visited = new boolean[MAX_N];
    static int[][] matrix = new int[MAX_N][MAX_N];
    static int cnt = 0;
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        E = sc.nextInt();
        
        for(int i = 0; i < E; i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            matrix[u][v] = matrix[v][u] = 1;
            
        }
        
        dfs(1);
        System.out.println(cnt - 1);
	}
	static void dfs(int node){
	    visited[node] = true;
	    cnt++;
	    
	    for(int next = 1; next < N + 1; next++){
	        if(!visited[next] && matrix[node][next] != 0){
	            dfs(next);
	        }
	    }
	}
}