백준 1260 - DFS와 BFS (JAVA)

백준 1260 - DFS와 BFS (JAVA)

DFS와 BFS를 한꺼번에 연습할 수 있는 좋은 문제네요.

앞으로 풀어갈 많은 DFS / BFS 문제의 초석이 될 문제이니

완벽하게 구현되도록 풀어보시면 좋겠네요.

 

www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

 

 

 

 

import java.util.*;
 
public class DFS_and_BFS {
 
    static int n, m, v;
    static boolean [] visits;
    static int [][] map;
    
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt(); //4
        m = sc.nextInt(); //5
        v = sc.nextInt(); //1
        visits = new boolean [n+1];
        map = new int [n+1][n+1];
        
        for(int i=1; i<=m; i++) {
            int temp1 = sc.nextInt(); //1
            int temp2 = sc.nextInt(); //2
            map[temp1][temp2] = 1;
            map[temp2][temp1] = 1;
        }
        
//        for(int i=1; i<=n; i++) { // 정상적으로 간선 입력 되었는지 확인
//            for(int j=1; j<=n; j++) {
//                System.out.print(map[i][j]+ " ");
//            }System.out.println();
//        }  
        
        dfs(v); //1
        
        System.out.println();
        
        visits = new boolean [n+1];
//        map = new int[n+1][n+1];
        
        bfs(v); //1
 
    }
    
    
    private static void dfs(int start) {
        visits[start] = true; //visits[1] = true
        System.out.print(start + " ");
        for(int i=1; i<=n; i++) {
            if (map[i][start] == 1 && visits[i]==false) {
                dfs(i);
            }
        }
    }
    
    private static void bfs(int start) {
        Queue<Integer> q = new LinkedList<Integer>();
        q.offer(start); // 1 
        while(!q.isEmpty()) {
            int out = q.poll();
            visits[out] = true;
            System.out.print(out + " ");
            for(int i=1; i<=n; i++) {
                if (map[i][out] == 1 && visits[i] == false && i!=out) { // 2 3 4 
                    q.offer(i);
                    visits[i] = true;
//                    System.out.println(Arrays.toString(q.toArray()));
                }
            }       
        }
    }
}