📝 백준1260 DFS와 BFS

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

1. 문제 요약

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하기
• 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고,
• 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
• 입력 :
  • 첫째줄
    • 정점의 개수 N(1 ≤ N ≤ 1,000),
    • 간선의 개수 M(1 ≤ M ≤ 10,000),
    • 탐색을 시작할 정점의 번호 V
  • 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호

2. 접근방법

공통사항

1. 그래프
   → 인접리스트(ArrayList<Integer>[])에 저장
   → DFS/BFS 구현 전에 인접리스트 오름차순 정렬하기 왜? 정점 번호가 작은 순서대로 방문
2. 방문 체크 배열 (boolean[] visited)
3. StringBuilder로 방문한 정점 순서기록하기 → 출력

DFS(깊이 우선탐색)

• 스택/재귀로 구현가능한데 여기서 재귀로 한 번 구현해보려고 한다
• ​현재 정점 방문 처리후 인접한 정점 순회하며 아직 방문하지 않은 정점에 대해 재귀 호출
• 재귀호출 순서 = 방문 순서

BFS(너비 우선 탐색)

• 큐를 사용해서 구현
• 큐에서 정점을 꺼낸 뒤, 그 정점과 연결된 아직 방문하지 않은 정점을 작은 번호순으로 큐에 넣는다
• 이렇게 해야 BFS에서도 작은 번호부터 방문을 하게 된다.

3. 오답코드

/*
Welcome to JDoodle!

You can execute code here in 88 languages. Right now you’re in the Java IDE.

  1. Click the orange Execute button ▶ to execute the sample code below and see how it works.

  2. Want help writing or debugging code? Type a query into JDroid on the right hand side ---------------->

  3.Try the menu buttons on the left. Save your file, share code with friends and open saved projects.

Want to change languages? Try the search bar up the top.
*/

import java.util.*;

public class Main {
    static ArrayList<Integer>[] graph; // 인접리스트
    static boolean[] visited; // 방문 체크
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt(); // 정점 개수
        int M = sc.nextInt(); // 간선 개수
        int V = sc.nextInt(); // 시작 정점
        
        // 0번 인덱스 안쓰고 1~N까지 쓰려고 이렇게 선언함
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 간선 입력하기
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 양방향이라서 a는 b연결, b에는 a연결
            graph[a].add(b);
            graph[b].add(a);
        }
        
        // 오름차순 정점 번호 작은 것부터
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
        }
        /*
        graph[0] = null
        graph[1] = [2, 3, 4]
        graph[2] = [1, 4]
        graph[3] = [1, 4]
        graph[4] = [1, 2, 3]
        */
        
        // DFS 
        visited = new boolean[N + 1];
        dfs(V);
        sb.append("\n");
        
        // BFS
        visited = new boolean[N + 1];
        bfs(V);
        
        System.out.println(sb.toString());
    }
    
    // DFS (재귀)
    static void dfs(int node) { // node는 현재 방문하고 있는 노드 번호 
        // node = V에서 시작
        // 방문 기록
        visited[node] = true;
        sb.append(node).append(" ");
        
        // 현재 정점의 인접 노드들을 하나씩 확인
        // 아직 안 가본 곳이면 DFS 재귀로 들어간다
        for (int next : graph[node]) { // 현재 정점 node와 연결된 모든 노드 리스트
            // 만약에 node = 1이고 grpah[1] = [2, 3, 4]면 next는 2, 3, 4
            // 현재 노드에서 갈 수 있는 인접 노드들을 하나씩 확인하기
            if (!visited[next]) {
                // 방문하지 않은 인접 노드 next로 재귀호출해서 이 노드부터 DFS 시작
                dfs(next);
            }
        }
    }
    
    // BFS (큐) 
    // 먼저 들어온 노드부터 처리하고 LinkedList를 Queue 인터페이스로 구현
    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start); // 시작 노드 큐에 넣고
        visited[start] = true; //방문 처리
        
        while (!q.isEmpty()) { 
            int node = q.poll(); // 먼저 들어온 노드 꺼내기
            sb.append(node).append(" ");
            
            // 인접 노드 탐색
            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
    }
}

자바 제네릭이랑 배열을 함께 사용할 때 자주 나오는 경고라고 한다. 

• 자바에서는 제네릭 배열 생성은 직접 불가하다. → 즉, new ArrayList[N+1]은 불가능 하기 때문에
• 제네릭을 빼고 그냥 Raw 타입 배열을 만들고 각 인덱스를 ArrayList<Integer>로 초기화한다.
• 이렇게 하면 컴파일러가 타입 안전성이 완전히 보장되지 않는다고 컴파일 에러를 띄운다. 
• 경고는 뜨지만, graph[i]에 타입이 일치하는 데이터만 들어오면 실제로 문제 없다고 한다. 

그냥 @SuppressWarnings("unchecked")로 경고만 제거하고 사용해도 되고 ArrayList를 (List<Integer>[])로 감싸서 타입캐스팅 하면 된다.

4. 정답코드

import java.util.*;

public class Main {
    /* static ArrayList<Integer>[] graph; */
    static List<Integer>[] graph; // 인접리스트
    static boolean[] visited; // 방문 체크
    static StringBuilder sb = new StringBuilder();
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt(); // 정점 개수
        int M = sc.nextInt(); // 간선 개수
        int V = sc.nextInt(); // 시작 정점
        
        // 0번 인덱스 안쓰고 1~N까지 쓰려고 이렇게 선언함
        /* 
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        } 
        */
        graph = (List<Integer>[]) new List[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }
        
        
        // 간선 입력하기
        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            // 양방향이라서 a는 b연결, b에는 a연결
            graph[a].add(b);
            graph[b].add(a);
        }
        
        // 오름차순 정점 번호 작은 것부터
        for (int i = 1; i <= N; i++) {
            Collections.sort(graph[i]);
        }
        /*
        graph[0] = null
        graph[1] = [2, 3, 4]
        graph[2] = [1, 4]
        graph[3] = [1, 4]
        graph[4] = [1, 2, 3]
        */
        
        // DFS 
        visited = new boolean[N + 1];
        dfs(V);
        sb.append("\n");
        
        // BFS
        visited = new boolean[N + 1];
        bfs(V);
        
        System.out.println(sb.toString());
    }
    
    // DFS (재귀)
    static void dfs(int node) { // node는 현재 방문하고 있는 노드 번호 
        // node = V에서 시작
        // 방문 기록
        visited[node] = true;
        sb.append(node).append(" ");
        
        // 현재 정점의 인접 노드들을 하나씩 확인
        // 아직 안 가본 곳이면 DFS 재귀로 들어간다
        for (int next : graph[node]) { // 현재 정점 node와 연결된 모든 노드 리스트
            // 만약에 node = 1이고 grpah[1] = [2, 3, 4]면 next는 2, 3, 4
            // 현재 노드에서 갈 수 있는 인접 노드들을 하나씩 확인하기
            if (!visited[next]) {
                // 방문하지 않은 인접 노드 next로 재귀호출해서 이 노드부터 DFS 시작
                dfs(next);
            }
        }
    }
    
    // BFS (큐) 
    // 먼저 들어온 노드부터 처리하고 LinkedList를 Queue 인터페이스로 구현
    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start); // 시작 노드 큐에 넣고
        visited[start] = true; //방문 처리
        
        while (!q.isEmpty()) { 
            int node = q.poll(); // 먼저 들어온 노드 꺼내기
            sb.append(node).append(" ");
            
            // 인접 노드 탐색
            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.add(next);
                }
            }
        }
    }
}

• List<Integer>[] graph → ArrayList 대신 List 인터페이스 사용
• graph = (List<Integer>[]) new List[N + 1]; → 제네릭 배열 생성 시 타입 캐스팅
• @SuppressWarnings("unchecked") → 컴파일러 경고 제거