[백준] DFS와 BFS 1260번 - Java

[백준] DFS와 BFS 1260번

나의 풀이

public class DfsAndBfs {
    static boolean[] visited;
    static int[][] matrix;
    static int N, M, V;

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        V = scanner.nextInt();

        matrix = new int[1001][1001];
        visited = new boolean[1001];

        for(int i = 0; i < M; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();

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

        dfs(V);
        System.out.println();
        visited = new boolean[1001];
        bfs(V);
    }

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

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

            for(int i = 1; i <= N; i++) {
                if(!visited[i] && matrix[node][i] == 1) {
                    queue.offer(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                }
            }
        }
    }

    static void dfs(int start) {
        visited[start] = true;

        System.out.print(start + " ");

        for(int i = 1; i <= N; i++) {
            if(matrix[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
}

public class DfsAndBfs {
    static boolean[] visited;
    static int[][] matrix;
    static int N, M, V;

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();
        V = scanner.nextInt();

        matrix = new int[1001][1001];
        visited = new boolean[1001];

        for(int i = 0; i < M; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();

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

• matrix, visited 는 값을 0이 아닌 1로 받기 위해 최대 범위 + 1 을 하여 초기화 해준다.
• 간선의 수만큼 반복하면서 x, y 좌표를 입력받아 서로 연결시켜준다.

    static void dfs(int start) {
        visited[start] = true;

        System.out.print(start + " ");

        for(int i = 1; i <= N; i++) {
            if(matrix[start][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
}

• dfs 는 재귀 & 스택을 이용한다. 여기서는 재귀를 사용
• 시작하는 노드를 방문처리 하고, 노드의 수만큼 반복하면서 해당 노드와 연결이 되어 있으면서, 방문한 적이 없는 노드를 재귀 호출한다.
• 연결되어있는 노드들을 모두 방문하면 재귀는 종료된다.

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

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

            for(int i = 1; i <= N; i++) {
                if(!visited[i] && matrix[node][i] == 1) {
                    queue.offer(i);
                    visited[i] = true;
                    System.out.print(i + " ");
                }
            }
        }
    }

• bfs 는 큐를 사용한다.
• 큐에 시작 노드를 담아주고 방문처리한다.
• 큐가 비어있지 않은동안 큐에서 노드를 빼고, 해당 노드와 연결되어 있으면서 방문하지 않은 노드를 모두 큐에 넣어주고, 방문처리한다.
• 연결되어있는 노드들을 모두 방문하면 bfs 는 종료된다.

        dfs(V);
        System.out.println();
        visited = new boolean[1001];
        bfs(V);

• dfs 먼저 실행 후 bfs 를 실행하기 위해 방문 기록을 초기화 해준다.