문제 1260

• DFS & BFS 설명 : DFS와 BFS

소스코드

import java.io.*;
import java.util.*;
public class boj1260 {
    static int[][] node = new int[1001][1001];
    static boolean[] visited = new boolean[1001];
    static int n;
    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());
        int m = Integer.parseInt(st.nextToken());
        int cur = Integer.parseInt(st.nextToken());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            node[a][b] = node[b][a] = 1;
        }
        dfs(cur);
        Arrays.fill(visited, false);
        System.out.println("");
        bfs(cur);
    }
    static void dfs(int x){
        if(visited[x]) return;
        visited[x] = true;
        System.out.print(x+" ");
        for (int i = 1; i < node.length; i++) {
            if(node[x][i] == 1){
                dfs(i);
            }
        }
    }
    static void bfs(int x){
        Queue<Integer> qu = new LinkedList();
        qu.offer(x);
        visited[x] =true;
        while(!qu.isEmpty()){
            x = qu.poll();
            System.out.print(x+" ");
            for (int i = 1; i < node.length; i++) {
                if(!visited[i] && node[x][i] == 1 ){
                    qu.offer(i);
                    visited[i] = true;
                }
            }
        }
    }
}

풀이 접근

1. 간선은 양방향으로 주어짐으로 해당 문제는 무방향 그래프이다.
2. 간선을 입력 받을 때, 양방향으로 node[x][y]를 1로 받아준다.
3. 접근 여부를 확인하기 위한 visited[]배열을 만들어 준다.
4. dfs 탐색을 먼저 출력하고, visited[]배열을 false로 초기화한 다음에 bfs 탐색을 출력한다.

문제 핵심

• BFS와 DFS를 구현 할 수 있는가!
• 양방향 그래프임을 캐치할 수 있는가!