[백준 / JAVA] 1260번 : DFS와 BFS

---

Comments

DFS와 BFS를 공부하는 중에, 쉬운 예제이지만 두개를 동시에 요구하는 문제가 있어서 한번 풀어봤다.

아래 코드가 길고 main은 초기화 / BFS메소드 / DFS 메소드로 딱 나뉘어져서 제목을 달아놨다.

0) static 변수들

각 노드에서 갈수 있는 노드를 인접리스트로 초기화 하는 것은 동일하지만, visited 배열은 따로 선언해야한다.

   - boolean[] dfsVisited / boolean[] bfsVisited

 

ArrayList<Integer> 형 배열 lists을 선언한다.

 

Queue<Integer> queue : BFS 알고리즘에서 사용할 Queue 자료구조 이다.

 

출력에 이용할 StringBuilder도 따로 선언했다.
( DFS가 모두 실행된 뒤에 BFS가 실행되기 때문에, 하나로 해도 되는데 그냥 보기좋게 두개로 했다. )

1) Main, 초기화 단계

• n : 노드의 수 / m : 간선의 개수 / start : 시작 노드
• visited 배열, lists 배열을 n+1 크기로 초기화해준다. ( 0번 인덱스는 안쓸거기 때문이다. )

중요 !!! - lists 배열의 각 인덱스들을 모두 new ArrayList<>()로 초기화 해줘야된다.

• 노드들의 인접노드를 나타낸 lists에 값에 값을 넣어주고, 정렬해준다.
• DFS() , BFS() 를 시작노드 start 값을 넣어서 돌려주고, 결과를 출력한다.

2) DFS

1. 만약 이미 방문한 노드라면 그냥 return 한다.
2. 방문한 노드가 아니면 방문배열을 true로 바꿔주고, StringBuilder에 추가해준다.
3. 해당 노드의 인접리스트를 돌면서 방문하지 않은 노드에 대하여 DFS()를 실행해준다. (재귀)

3) BFS

1. 맨 처음에 시작노드를 Queue에 넣어준다.
2. while문은 이제 Queue가 empty 될때까지 반복할 것이다.

(while문 내부 반복)

3. 일단 꺼낸다. 꺼내면서 그 값을 저장해야한다. (poll()메소드는 값을 반환하는 기능도 갖고있다.)
4. 이번now꺼냈는데, 아직 방문배열이 false로 되어있다면 StringBuilder에 추가해주고, 방문배열을 true로 바꿔준다.
5. now 노드의 인접리스트를 돌면서 방문하지 않은 노드가 있다면 Queue에 넣어준다.,
6. 반복

---

Code

1) Main : 초기화 단계

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class No1260 {
    //1260번 : DFS와 BFS
    static boolean[] dfsVisited;
    static boolean[] bfsVisited;
    static ArrayList<Integer>[] lists;
    static Queue<Integer> queue = new LinkedList<>();
    static StringBuilder dfsBuilder = new StringBuilder();
    static StringBuilder bfsBuilder = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());
        dfsVisited = new boolean[n+1];
        bfsVisited = new boolean[n+1];
        lists = new ArrayList[n+1];

        for(int i=0;i<=n;i++){
            lists[i] = new ArrayList<>();
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());

            lists[node1].add(node2);
            lists[node2].add(node1);
        }

        for(int i=1;i<=n;i++){
            Collections.sort(lists[i]);
        }

        DFS(start);
        BFS(start);

        System.out.println(dfsBuilder);
        System.out.println(bfsBuilder);

    }

2) DFS

    public static void DFS(int node){
        if(dfsVisited[node]) return;

        dfsVisited[node] = true;
        dfsBuilder.append(node+" ");
        for(int i : lists[node]){
            if(!dfsVisited[i]){
                DFS(i);
            }
        }
    }

3) BFS

    public static void BFS(int node){
        queue.offer(node);

        while(!queue.isEmpty()){
            int now = queue.poll();

            if(!bfsVisited[now]){
                bfsBuilder.append(now+" ");
            }
            bfsVisited[now] = true;

            for(int i : lists[now]){
                if(!bfsVisited[i]){
                    queue.offer(i);
                }
            }
        }
    }
// -----------------------------
}//public class No1260 닫는 괄호