(JAVA) 백준온라인 - 1260번 DFS와 BFS

학교에서 그래프 탐색을 배우기는 했지만 사실 이론만 배우고 직접 구현하는 것은 하지 않았다. 

다시 구글링하고 유튜브를 보며 이해를 하였다. 하지만 직접 구현하기 어려워서 구글링으로 문제를 검색을 하여서 이해를 하였다. 다시 풀어 볼 예정이다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int node[][]; //인접행렬 배열
    static int check[]; // 노드의 방문 여부 표시 배열
    static Queue<Integer> queue = new LinkedList<>(); //BFS를 위한 큐
    static void dfs(int x) { //DFS 메소드 재귀호출 반복
        if(check[x] == 1) return; // 이미 방문한 노드라면 종료.

        check[x] = 1; //방문하지 않은 노드라면 방문 여부를 표시하고 출력
        System.out.print(x+" ");
        for(int i = 1; i<node.length; i++){// 인접행렬의 경우 행렬이 대각선을 기준으로 대칭이 되므로 행 또는 열을 기준으로만 탐색
            if(node[x][i]==1){//방문하지 않은 노드의 인접 노드일 경우
                dfs(i);
            }
        }
    }

    static void bfs(int x){ //BFS 메소드 큐를 이용해 구현
        queue.offer(x); // 큐에 시작 노드 삽입
        check[x] = 1; //시작 노드를 방문 표시
        while(!queue.isEmpty()){//공백큐가 될 떄까지 반복
            x = queue.poll(); //큐에서 하나 꺼낸다.
            System.out.print(x+" ");// 출력
            for(int i = 1; i<node.length; i++){ // 큐에서 꺼낸 노드와 연결된 노드를 탐색
                if(check[i]!=1 && node[x][i] == 1){// 큐에서 꺼낸 노드와 연결된 노드가 방문하지 않았던 노드라면?
                    queue.offer(i); //큐에 삽입 후
                    check[i] = 1; //방문 표시
                }

            }

        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //정점의 개수
        int m = sc.nextInt(); //간선의 개수
        int v = sc.nextInt(); //탐색 시작 노드

        node = new int[n+1][n+1];
        check = new int[n+1];

        for(int i = 0; i<m; i++){ // 인접행렬로 그래프를 구현
            int a = sc.nextInt();
            int b = sc.nextInt();
            node[a][b] = 1;
            node[b][a] = 1;
        }

        dfs(v);
        Arrays.fill(check, 0); //DFS이후 동일한 방문 여부배열을 사용하기 때문에 다시 0으로 초기화 해준다.
        System.out.println("");
        bfs(v);
    }
}

구글링을 해서 베꼈지만 다시 내 힘으로 풀어서 다시 업로드 할 예정이다.