🥈[백준, 1260] DFS와 BFS (Java)

 

문제 링크

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

난이도

 

시간제한

2초

 

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

 

출력

첫째 줄에 DFS를 수행한 결과를, 그다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

입출력 예시 1

입력 

4 5 1
1 2
1 3
1 4
2 4
3 4

출력

1 2 4 3
1 2 3 4

 

입출력 예시 2

입력

5 5 3
5 4
5 2
1 2
3 4
3 1

출력

3 1 2 5 4
3 1 4 2 5

 

입출력 예시 3

입력

1000 1 1000
999 1000

 

출력

1000 999
1000 999

---

문제 풀이 과정

그래프를 표현하는 방식은 인접 행렬과 인접 리스트 2가지가 있다.

자세한 설명은 아래 블로그를 참고하길 바란다.

[알고리즘] Graph

 

1. 인접 행렬을 통한 구현

입력 값 저장하기

 

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 V = Integer.parseInt(st.nextToken());

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

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());

    int num1 = Integer.parseInt(st.nextToken());
    int num2 = Integer.parseInt(st.nextToken());

    graph[num1][num2] = 1;
    graph[num2][num1] = 1;
}

 

인접 행렬에서 서로 인접한 경우는 1로 표기하고 그렇지 않은 경우에는 0으로 표기한다. 따라서 간선이 연결하는 두 정점의 번호를 입력받아 graph에 저장한다.

 

입출력 예시 1의 경우 이처럼 인접 행렬이 표기된다.

 

 

dfs 함수 구현

 

public class BOJ_1260_1 {
    static int N;
    static int[][] graph;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    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 V = Integer.parseInt(st.nextToken());

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

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            graph[num1][num2] = 1;
            graph[num2][num1] = 1;
        }
    }
}

dfs는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 1부터 정점의 개수만큼 반복문을 돌며 graph의 값이 1이고(연결된 정점이고) 방문하지 않은 경우에 해당 노드에 대한 dfs함수를 호출하는 방식으로 구현했다.

 

bfs함수 구현

 

static void bfs(int n) {
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(n);
    visited[n] = true;

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

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

bfs는 가까운 노드부터 탐색하는 알고리즘이다. 처음 시작 노드를 큐에 삽입하고 방문 처리를 한다. 그 후 큐에 노드가 있는 동안 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리를 한다. 해당 과정을 반복하며 모두 탐색하면 종료된다.

 

최종 코드

 

public class BOJ_1260_1 {
    static int N;
    static int[][] graph;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    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 V = Integer.parseInt(st.nextToken());

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

        // 인접 행렬로 그래프 구현
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            graph[num1][num2] = 1;
            graph[num2][num1] = 1;
        }

        visited = new boolean[N + 1];
        dfs(V);
        sb.append("\n");

        visited = new boolean[N + 1];
        bfs(V);
        System.out.println(sb);
    }

    static void dfs(int n) {
        visited[n] = true;
        sb.append(n).append(" ");

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

    static void bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(n);
        visited[n] = true;

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

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

dfs와 bfs를 수행한 결과를 함께 출력해야 하므로 StringBuilder()를 사용하여 출력했다.

 

 

 

2. 인접 리스트를 통한 구현

인접 행렬과 같은 부분의 구현에 대한 설명은 생략하겠다.

 

입력 값 저장하기

 

public class BOJ_1260_2 {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
		...

        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            graph.get(num1).add(num2);
            graph.get(num2).add(num1);
        }
    }
}

각 정점마다 연결된 정점의 번호를 저장해야 하므로 ArrayList<ArrayList<Integer>>의 타입으로 그래프가 구성된다.

반복문을 돌며 연결된 정점의 번호를 저장하는데 처음 저장하는 경우에 graph.get()을 수행하기 위해 각 정점의 ArrayList의 초기화가 필요하다. 

 

입출력 예시 1의 경우 이처럼 인접 리스트가 표기된다.

 

❗여기서 주의할 점!!

문제에 "방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것은 먼저 방문한다."라는 조건이 있다.

인접 행렬의 경우 이를 고려하지 않아도 되었지만 인접 리스트에서는 저장한 순서대로 탐색이 진행되기 때문에 이를 고려해야 한다.

 

예제 1의 경우 순서대로 입력 값이 들어와 따로 정렬이 필요 없지만, 예제 2를 살펴보면 정점의 크기가 정렬이 되지 않은 채로 입력 값으로 주어진 것을 볼 수 있다.

 

for (int i = 1; i <= N; i++) {
    Collections.sort(graph.get(i));
}

이와 같이 각 정점에 인접하는 정점 번호를 오름차순으로 정렬한다.

 

dfs 함수 구현

 

static void dfs(int n) {
    visited[n] = true;
    sb.append(n).append(" ");

    for (int i = 0; i < graph.get(n).size(); i++) {
        int num = graph.get(n).get(i);

        if (!visited[num]) {
            dfs(num);
        }
    }
}

각 정점에 인접하는 정점 개수만큼 반복문을 돌며 해당 노드를 방문하지 않았을 경우 dfs함수를 호출하여 탐색을 진행했다.

 

bfs함수 구현

 

static void bfs(int n) {
    Queue<Integer> queue = new LinkedList<>();

    queue.offer(n);
    visited[n] = true;

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

        for (int i = 0; i < graph.get(node).size(); i++) {
            int linkNode = graph.get(node).get(i);

            if (!visited[linkNode]) {
                queue.offer(linkNode);
                visited[linkNode] = true;
            }
        }
    }
}

설명은 인접 행렬과 같다.

 

최종 코드

 

public class BOJ_1260_2 {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());

        // 그래프 초기화
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프에 입력 값 저장
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            graph.get(num1).add(num2);
            graph.get(num2).add(num1);
        }

        // 정점 번호를 오름차순으로 정렬
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph.get(i));
        }

        visited = new boolean[N + 1];
        dfs(V);
        sb.append("\n");

        visited = new boolean[N + 1];
        bfs(V);
        System.out.println(sb);
    }

    static void dfs(int n) {
        visited[n] = true;
        sb.append(n).append(" ");

        for (int i = 0; i < graph.get(n).size(); i++) {
            int num = graph.get(n).get(i);

            if (!visited[num]) {
                dfs(num);
            }
        }
    }

    static void bfs(int n) {
        Queue<Integer> queue = new LinkedList<>();

        queue.offer(n);
        visited[n] = true;

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

            for (int i = 0; i < graph.get(node).size(); i++) {
                int linkNode = graph.get(node).get(i);

                if (!visited[linkNode]) {
                    queue.offer(linkNode);
                    visited[linkNode] = true;
                }
            }
        }
    }
}