[BOJ] 1260번 : DFS와 BFS

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

1260번: DFS와 BFS

 

 

알고리즘 분류 : BFS, DFS

 

public class Main {
    static Myscanner sc = new Myscanner();
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    static int[][] adj = new int[1001][1001];
    static final int inf = Integer.MAX_VALUE;
    static boolean[] Dvisited = new boolean[1001];
    static boolean[] Bvisited = new boolean[1001];
    public static void main(String[] args) {

        int N = sc.nextInt();
        int M = sc.nextInt();
        int V = sc.nextInt();
        //adj 초기화
        for(int r =0; r<1001;r++){
            for(int c= 0; c<1001;c++){
                adj[r][c] = (r == c ? 0 : inf);
                
            }
        }
        for(int idx = 0; idx<M;idx++)
        {
            int s = sc.nextInt();
            int e = sc.nextInt();
            adj[s][e]=adj[e][s] =1;
        }
        out.print(V);
        DFS(V);
        out.println();
        out.print(V);
        BFS(V);
        out.close();
    }

    private static void DFS(int v) {
        Dvisited[v] = true;
        
        for(int idx =1;idx<adj[0].length;idx++){
            if((adj[v][idx]!=inf && adj[v][idx]!=0) && (!Dvisited[idx])){
                out.print(" " + idx);
                DFS(idx);
            }
        }
        
        
    }

    private static void BFS(int v) {
        
        Queue<Integer> q = new LinkedList<>();
        Bvisited[v] = true;
        q.offer(v);
        
        while(!q.isEmpty())
        {
            int size = q.size();
            for(int sz = 0; sz<size;sz++)
            {
                int here = q.poll();
                
                for(int idx = 1; idx<adj[0].length;idx++)
                {
                    if((adj[here][idx]!=inf && adj[here][idx]!=0) && (!Bvisited[idx])){
                        q.offer(idx);
                        Bvisited[idx]= true;
                        out.print(" "+idx);
                    }
                }                
            }
        }
    }
}

 

BFS와 DFS의 정석을 물어보는 문제인 것 같다.

DFS는 재귀로, BFS는 Queue를 이용하여 해결 완료!