백준 1260번 DFS와 BFS

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

1260번: DFS와 BFS

DFS(Depth First Search, 깊이우선탐색)

깊이 우선 탐색은 노드의 깊이가 깊은 순서를 먼저 탐색하는 알고리즘이다.

DFS 알고리즘은 인접행렬 자료구조와 재귀 알고리즘을 사용해서 구현한다.

 

BFS(Breadth First Search, 너비우선탐색)

너비 우선 탐색은 같은 깊이의 노드를 먼저 탐색하는 알고리즘이다. 

BFS 알고리즘은 Queue 자료구조를 사용해서 구현한다.

 

import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class P1260_DFS와BFS {
    static int[][] branch;    //간선 연결 상태
    static boolean[] visit; //확인 여부
    static int n; //정점개수
    static int m; //간선개수
    static int start; //시작정점
    public static Queue<Integer> queue;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();       //정점 개수
        m = sc.nextInt();       //간선 개수
        start = sc.nextInt();   //시작할 정점의 번호

        branch = new int[1001][1001];
        visit = new boolean[1001];

        //간선 연결 상태 저장하기
        for(int i = 0 ; i < m; i++){
            int x = sc.nextInt();
            int y = sc.nextInt();

            branch[x][y] = branch[y][x] = 1;
        }

        dfs(start);

        visit = new boolean[1001];    //bfs를 위해 상태 초기화
        System.out.println();

        bfs(start);
    }

    public static void dfs(int start){
        visit[start] = true;
        System.out.print(start + " ");
        for(int i = 1; i <= n; i++){
            if(branch[start][i] == 1 && visit[i] == false){
                dfs(i);
            }
        }
    }

    public  static void bfs(int start) {
        queue = new LinkedList<Integer>();
        queue.add(start);
        visit[start] = true;
        System.out.print(start + " ");

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

            for(int i = 1; i <branch.length; i++){
                if(branch[temp][i] == 1 && visit[i] == false){
                    queue.add(i);
                    visit[i] = true;
                    System.out.print(i + " ");
                }
            }
        }
    }
}

 

후기

구글링으로 여기저기서 코드 긁어와서 했는데 정말 어렵다.

일단 DFS, BFS 개념부터 다시 정리할 필요가 있을거 같다.

정말 기초가 부족하구나를 코드 한줄 적을때 마다 느낀다.. 반성하세요