[Java] BFS / DFS 인접리스트와 재귀

공통코드 (Main)

static int N;
    static boolean adjMatrix[][];

    public static void main(String[] args) throws FileNotFoundException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt(); // 정점수
        int C = sc.nextInt(); // 간선수

        adjMatrix = new boolean[N][N]; // 0으로 초기화된 상태
        for (int i = 0; i < C; ++i) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            adjMatrix[to][from] = adjMatrix[from][to] = true;
        }

        bfs();
        dfs(0, new boolean[N]);

    }

BFS

💡 인접리스트 이용

private static void bfs() {
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean visited[] = new boolean[N];

        // 0 정점을 작점으로
        visited[0] = true; // 방문처리
        queue.offer(0); // 큐에 추가

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            System.out.print((char) (cur + 65));

            // 현 정점의 인접정점들에 큐에 넣어서 차후 탐색하도록 만들기
            for (int i = 0; i < N; i++) {
                if (adjMatrix[cur][i] && !visited[i]) { // 방문을 하지 않고, 현재 정점에서 그 정점으로 갈 수 있는지
                    visited[i] = true;
                    queue.offer(i);
                }
            }
        }
        System.out.println();
    }

---

DFS

💡 재귀로 구현

private static void dfs(int current, boolean[] visited) {

        visited[current] = true; //방문처리
        System.out.print((char) (current + 65));

        for (int i = 0; i < N; ++i) {
            if (adjMatrix[current][i] && !visited[i]) {
                dfs(i, visited);
            }
        }
    }
}