[BAEKJOON] 1260. DFS와 BFS (JAVA)

:D 문제

---

문제

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

입력

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

출력

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

Baekjoon

1260번: DFS와 BFS

 

 

:D 풀이 방법

---

 

 

두 점의 연결여부를 확인하기 위해 인접 행렬을 사용했다.

[예제 입력 2]와 같이 입력이 주어졌을 때, N(정점의 수)+1 크기의

2차원 배열을 생성해 다음과 같이 두 점의 연결 정보를 저장하였다.

 

isVisited라는 boolean []을 만들어 방문 여부를 저장하였고 두 가지 배열을 이용해 BFS와 DFS를 진행했다.

 

 

 

 

 

 

:D 작성 코드

---

DFS는 해당 정점(V)의 방문 여부를 체크하고, V가 방문할 수 있는 정점을 재귀 호출을 사용해 구현하였다.

BFS는 큐(Queue)에 V를 저장/제거해가며, V가 방문할 수 있는 정점들을 저장하여 해결했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Solution1260H {
    static int N, M; // N: 정점의 수, M: 간선의 수
    static StringBuilder answer;
    static int[][] graph; // [N+1][N+1] 크기의 배열
    static Queue<Integer> tmp; // BFS에 사용할 큐

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(input);
        
        N = Integer.parseInt(tokenizer.nextToken());
        M = Integer.parseInt(tokenizer.nextToken());
        int V = Integer.parseInt(tokenizer.nextToken());

        graph = new int[N + 1][N + 1];
        boolean[] isVisited = new boolean[10001];

        // 인접 행렬 생성
        for (int i = 1; i <= M; i++) {
            input = br.readLine();
            tokenizer = new StringTokenizer(input, " ");
            int x = Integer.parseInt(tokenizer.nextToken());
            int y = Integer.parseInt(tokenizer.nextToken());
            graph[x][y] = graph[y][x] = 1;
        }

        // DFS 출력
        answer = new StringBuilder();
        dfs(isVisited, V);
        System.out.println(answer);

        // BFS 출력
        answer = new StringBuilder();
        isVisited = new boolean[1001];
        tmp = new ArrayDeque<>();
        bfs(V, isVisited);
        System.out.print(answer);
    }
    
    /** DFS 구현부 **/
    private static void dfs(boolean[] isVisited, int v) {
        isVisited[v] = true;
        answer.append(v).append(" ");

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

    /** BFS 구현부 **/
    private static void bfs(int v, boolean[] isVisited) {

        tmp.add(v);
        isVisited[v] = true;

        while (!tmp.isEmpty()) {
            int curNum = tmp.poll();
            answer.append(curNum + " ");

            for (int i = 1; i <= N; i++) {
                if (graph[curNum][i] == 1 && !isVisited[i]) {
                    tmp.add(i);
                    isVisited[i] = true;
                }
            }
        }
    }
}

 

마무리

어떻게 구현해야 할지 고민하느라 시간을 많이 쓴 것 같다. 한번 했으니 까먹지 않게 꾸준히 해봐야겠다.