[백준]1260: DFS와 BFS

1학기 종료 후,,, 오랜만에 백준을 풀기 시작했습니다... DFS와 BFS 정복해볼게요.

---

DFS는 한놈만 팬다,,,, 재귀!

BFS는 층별로 본다,,,, 큐로 구현, 최단거리 구하기!!!

---

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Q1260 {
    static int[][] edge_Arr;
    static boolean[] visited_Arr;
    static int N, M, V, count;
    static Queue<Integer> que = new LinkedList<>();

    public static void BFS(int start) {
        que.offer(start);
        visited_Arr[start] = true;
        System.out.print(start + " ");

        while (!que.isEmpty()) {
            start = que.poll();

            for (int i = 1; i <= N; i++) {
                if (edge_Arr[start][i] == 1 && visited_Arr[i] == false) {
                    que.offer(i);
                    visited_Arr[i]=true;
                    System.out.print(i + " ");
                }
            }
        }

    }

    public static void DFS(int start) {
        visited_Arr[start]=true;
        System.out.print(start + " ");
        if (count == N) {
            return;
        }
        count++;

        for (int i = 1; i <= N; i++) {
            if (edge_Arr[start][i] == 1 && visited_Arr[i] == false) {
                DFS(i);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        edge_Arr=new int[N+1][N+1];
        visited_Arr = new boolean[N+1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int row = Integer.parseInt(st.nextToken());
            int col = Integer.parseInt(st.nextToken());
            edge_Arr[row][col] = edge_Arr[col][row] = 1;
        }
        DFS(V);
        System.out.println();
        visited_Arr = new boolean[N+1];
        BFS(V);
    }
}

 

순차적으로 알아보도록 하장..

---

DFS

public static void DFS(int start) {
    visited_Arr[start]=true;
    System.out.print(start + " ");
    if (count == N) {
        return;
    }
    count++;

    for (int i = 1; i <= N; i++) {
        if (edge_Arr[start][i] == 1 && visited_Arr[i] == false) {
            DFS(i);
        }
    }
}

visited 배열을 만들어서 방문한 순간 true로 바꿔준다.

->

출력을 해준다.

->

count가 끝에 도달하면 return 해준다.

->

1번째 부터 N번째 까지 돌면서 만약 간선이 존재하고 그 점을 visit하지 않았다면(visited배열 값이 false) DFS로 재귀!

---

BFS

public static void BFS(int start) {
    que.offer(start);
    visited_Arr[start] = true;
    System.out.print(start + " ");

    while (!que.isEmpty()) {
        start = que.poll();

        for (int i = 1; i <= N; i++) {
            if (edge_Arr[start][i] == 1 && visited_Arr[i] == false) {
                que.offer(i);
                visited_Arr[i]=true;
                System.out.print(i + " ");
            }
        }
    }

}

que를 선언해서 start값을 바로 넣어줘서 시작한다!!!, visited를 참으로 바꿔준다!

->

while 문 엔딩 조건은 큐가 비었을때!!!

->

start값을 que에서 poll 한 값으로 초기화!!!

->

for문으로 1번째부터 N번째까지 돈다, 간선이 존재하고 아직 방문하지 않았다면 

->

que에 그 점 넣어주고 visited값도 true로 바꿔준다!!!

->

반복문으로 반복!!!!

---

,,,,잘해보장,,,,