백준-1260번/DFS와 BFS(java)

 

 

문제 이해

 

그래프에서 DFS(깊이 우선 탐색) 와 BFS(너비 우선 탐색) 을 구현하면 되는 문제이다.

 

그래프를 구현하는 방법에는 인접행렬과 연결리스트로 표현하는 것이 있는데 이번 문제에서는 연결리스트로 구현해 보았다.

 

문제 풀이

 

1) ArrayList만들어주기

ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

 

2) 각 노드 별 리스트를 만들어준다.

for(int i=0; i<=N; i++){
    graph.add(new ArrayList<>());
}

 

3) 각 노드들의 연결 정보를 입력 받는다.

for(int i=0; i<M; i++){
    int x=scanner.nextInt();
    int y=scanner.nextInt();
    putEdge(graph,x,y);
}

<putEdge 메서드>

public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y){
    graph.get(x).add(y);
    graph.get(y).add(x);
}

 

 

4) *** 각 노드에 있는 연결 리스트를 정렬해준다.(정렬을 안해도 DFS와 BFS의 성질에 어긋나지는 않지만 정렬을 한 후 실행해야 백준에서는 정답으로 인정됨)

for(int i=0; i<=N; i++){ //ArrayList 정렬
    Collections.sort(graph.get(i));
}

 

 

6) dfs

public static void dfs(ArrayList<ArrayList<Integer>> graph, int x){
    visit[x]=true;

    System.out.print(x + " ");

    for(int y :  graph.get(x)){
        if(!visit[y]){
            dfs(graph,y);
        }
    }
}

방문하면 visit를 true로 바꿔주고 인접한 노드로 방문하는 것을 반복한다.

 

 

7) bfs

public static void bfs(ArrayList<ArrayList<Integer>> graph, int x){
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(x);
    visit[x]=true;

   while(!queue.isEmpty()){
       int y = queue.poll();
       System.out.print(y + " ");

       for(int j : graph.get(y)){
           if(!visit[j]){
               queue.offer(j);
               visit[j]=true;
           }
       }
   }

}

 

bfs는 Queue를 이용한다.

<bfs 순서>

1) 노드 방문, 방문한 노드 Queue에 삽입

 

2) 가장 먼저  Queue에 들어온 노드를 제거, 제거한 노드와 인접한 노드 Queue에 삽입

 

3) 2)번 과정을 Queue가 빌때까지 반복한다.

 

 

<전체 코드>

 

import java.util.*;

public class Problem1260 {
    static int N;
    static int M;
    static int V;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N=scanner.nextInt();
        M=scanner.nextInt();
        V=scanner.nextInt();

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        visit = new boolean[N+1];

        for(int i=0; i<=N; i++){
            graph.add(new ArrayList<>()); //각 노드 별 리스트를 만들어준다.
        }

        for(int i=0; i<M; i++){
            int x=scanner.nextInt();
            int y=scanner.nextInt();
            putEdge(graph,x,y);
        }

        for(int i=0; i<=N; i++){ //ArrayList 정렬
            Collections.sort(graph.get(i));
        }


        dfs(graph,V);
        System.out.println();
        Arrays.fill(visit,false);
        bfs(graph,V);


    }

    public static void putEdge(ArrayList<ArrayList<Integer>> graph, int x, int y){
        graph.get(x).add(y);
        graph.get(y).add(x);
    }

    public static void dfs(ArrayList<ArrayList<Integer>> graph, int x){
        visit[x]=true;

        System.out.print(x + " ");

        for(int y :  graph.get(x)){
            if(!visit[y]){
                dfs(graph,y);
            }
        }
    }
    public static void bfs(ArrayList<ArrayList<Integer>> graph, int x){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        visit[x]=true;

       while(!queue.isEmpty()){
           int y = queue.poll();
           System.out.print(y + " ");

           for(int j : graph.get(y)){
               if(!visit[j]){
                   queue.offer(j);
                   visit[j]=true;
               }
           }
       }

    }
}