[java] 백준 알고리즘 1260번 DFS와 BFS 풀이

깊이 우선 탐색, 너비 우선 탐색에 대한 문제였다.

이 개념들은 나도 모르던 개념이라 다른 분들의 블로그를 참고해서 구현하고 공부했다.

참고 블로그: DFS, BFS

* 풀이 소스

public class Baekjoon1260 {
 
    private static boolean[] visited;
    private static int[][] adjacencyMatrix;
    private static Queue<Integer> queue;
    private static int vertex;
    private static StringBuilder sb;
    
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        sb = new StringBuilder();
        
        vertex = Integer.parseInt(st.nextToken()); // 정점
        int edge = Integer.parseInt(st.nextToken()); // 간선
        int startPoint = Integer.parseInt(st.nextToken()); // 탐색을 시작할 정점의 번호
        visited = new boolean[vertex+1]; // 방문했는지 체크 배열
        Arrays.fill(visited, false);
        
        adjacencyMatrix = new int[vertex+1][vertex+1]; // 인접배열
        
        for(int i=0; i<edge; i++) {
            st = new StringTokenizer(br.readLine());
            int firstVertex = Integer.parseInt(st.nextToken());
            int secondVertex = Integer.parseInt(st.nextToken());
            adjacencyMatrix[firstVertex][secondVertex] = adjacencyMatrix[secondVertex][firstVertex] = 1;
        }
        DFS(startPoint);
        sb.append("\n");
        
        queue = new LinkedList<>();
        Arrays.fill(visited, false);
        BFS(startPoint);
        
        bw.write(sb.toString());
        bw.flush();
    }    
    
    private static void DFS(int startPoint) {
        
        visited[startPoint] = true;
        sb.append(startPoint+" ");
        
        for(int i=1; i<=vertex; i++) {
            
            if(adjacencyMatrix[startPoint][i] == 1 && !visited[i]) {
                DFS(i);
            }
        }
    }
    
    private static void BFS(int startPoint) {
        
        queue.add(startPoint);
        
        visited[startPoint] = true;
        
        while(!queue.isEmpty()) {
            
            startPoint = queue.poll();
            sb.append(startPoint+" ");
            
            for(int i=1; i<=vertex; i++) {
                
                if(adjacencyMatrix[startPoint][i] == 1 && !visited[i]) {
                    
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}