(#1260 Java) DFS와 BFS

 

문제 해결

 

그냥 대놓고 BFS와 DFS를 구하라고 하는 문제이다.

그냥 전형적인 방식으로 수월하게 코드를 작성하고 있었는데, 생각보다 꽤 많은 문제에 부딪혔다.

 

우선 Gragh와 Visited 배열을 main함수 밖에 크기까지 선언해서 계속 범위 오류가 났다.

이 부분을 주의해서 코드를 보면 좋을 것 같다.

 

또한, 원래 dfs를 구현할 때 재귀를 이용하는 게 훨씬 쉽지만, 이번에는 스택을 이용했다가, 문제에서 요구하는 작은 번호의 정점을 먼저 방문하는 조건을 충족하지 못 해 그냥 추가적인 코드를 짜지 않고 재귀를 이용하는 코드로 바꿨다...ㅎ

이런 식으로 작은 정점부터 들르지 않는 결과가 나왔다.

 

 

 

먼저 크기를 정하지 않고 static으로 main 함수 밖에 변수들을 선언해준다.

static final int Max_N = 1000;
static int N, M, V; // 정점, 간선, 시작할 정점의 번호
static int[][] Gragh;
static boolean[] Visited;

 

 

그리고 DFS/BFS 문제에서 항상 하던대로 main 함수를작성해준다.

여기에서 노드의 개수를 입력 받은 후 Graph의 크기를 선언해주고, dfs함수를 호출한 후 Visited 배열도 초기화해주어야 한다. 난 이 부분을 놓쳐서 계속 오류가 났다

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    N = in.nextInt();
    M = in.nextInt();
    V = in.nextInt();

    Gragh = new int[N+1][N+1];

    for(int i = 0; i < M; i++) {
        int u = in.nextInt();
        int v = in.nextInt();
        Gragh[u][v] = Gragh[v][u] = 1;
    }

    Visited = new boolean[N+1];
    dfs(V);

    System.out.println();

    Visited = new boolean[N+1];
    bfs(V);
}

 

 

그리고 dfs는 재귀를 bfs는 큐를 이용해 작성해주었다.

아까 말한대로 스택을 이용해 구현했다가 작은 번호의 정점부터 들르는 조건을 만족하지 못해 일단 재귀로 방법을 바꿔 구현해주었다. (재귀가 훨씬 간단하기도 하고..)

static void dfs(int node){ //재귀 이용

    Visited[node] = true;
    System.out.print(node+" ");

    for (int i = 0; i <= N; i++) {
        if(!Visited[i] && Gragh[node][i] == 1)
            dfs(i);
    }
}

static void bfs(int node){ //큐 이용

    Queue<Integer> myqueue = new LinkedList<>();
    Visited[node] = true;
    myqueue.add(node);

    while (!myqueue.isEmpty()){
        int curr = myqueue.remove();
        System.out.print(curr+" ");

        for (int i = 0; i <= N; i++) {
            if(!Visited[i] && Gragh[curr][i] == 1) {
                Visited[i] = true;
                myqueue.add(i);
            }
        }
    }
}

 

 

최종 코드

 

package org.example.DfsBfs;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class DfsBfs {

    static final int Max_N = 1000;
    static int N, M, V; // 정점, 간선, 시작할 정점의 번호
    static int[][] Gragh;
    static boolean[] Visited;

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        V = in.nextInt();

        Gragh = new int[N+1][N+1];

        for(int i = 0; i < M; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            Gragh[u][v] = Gragh[v][u] = 1;
        }

        Visited = new boolean[N+1];
        dfs(V);

        System.out.println();

        Visited = new boolean[N+1];
        bfs(V);
    }


    static void dfs(int node){ //재귀 이용

        Visited[node] = true;
        System.out.print(node+" ");

        for (int i = 0; i <= N; i++) {
            if(!Visited[i] && Gragh[node][i] == 1)
                dfs(i);
        }
    }
    
    static void bfs(int node){ //큐 이용

        Queue<Integer> myqueue = new LinkedList<>();
        Visited[node] = true;
        myqueue.add(node);

        while (!myqueue.isEmpty()){
            int curr = myqueue.remove();
            System.out.print(curr+" ");

            for (int i = 0; i <= N; i++) {
                if(!Visited[i] && Gragh[curr][i] == 1) {
                    Visited[i] = true;
                    myqueue.add(i);
                }
            }
        }
    }
}