[JAVA] 백준 1260번: DFS와 BFS

 

---

문제

• 정점 개수, 간선 개수, 탐색을 시작할 정점의 번호가 주어질 때, DFS로 탐색한 순서와 BFS로 탐색한 순서를 출력하는 문제.

 

아이디어

• 2차원 배열을 이용해 그래프를 구현한다.
  • graph[n][n] 으로 구현한다.
  • graph[n1][n2] = true : n1과 n2가 연결되어 있다.
• 입력 받는 M개의 간선을 통해 노드끼리 양방향으로 연결한다.
• 배열은 0부터 시작하므로, 인덱스 처리를 쉽게 하기 위해 입력받은 수에서 1씩 뺀 요소에 갱신한다. 
  • 1, 2 입력
  • graph[0][1] = true
  • graph[1][0] = true
• 이후 DFS, BFS 탐색을 수행한다.
• 중요한 점은 DFS를 수행한 후 BFS를 수행하기 전에 반드시 visited boolean 배열이 초기화 되어야 한다는 점이다.
• 또 잊지 말아야 할 점은, 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문해야 한다는 점이다.

 

풀이

import java.io.*;
import java.util.*;

public class Main {
    static boolean[][] graph;
    static boolean[] visited;
    static int N, M, V;
    
    // bfs에서 사용할 큐 선언
    static Deque<Integer> queue = new ArrayDeque<>();
    
    // 결과값을 저장할 StringBuilder 선언
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        graph = new boolean[N][N];
        visited = new boolean[N];
        
        // 그래프 양방향 연결
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken())-1;
            int n2 = Integer.parseInt(st.nextToken())-1;
            graph[n1][n2] = true;
            graph[n2][n1] = true;
        }
        
        // dfs 수행
        dfs(V);
        sb.append('\n');
        
        // visited 배열 초기화
        visited = new boolean[N];
        
        // bfs 수행
        bfs();

        System.out.println(sb);
    }
    
    // dfs
    static void dfs(int node) {
        visited[node] = true;
        sb.append(node+1).append(' ');
        for(int i=0; i<N; i++) {
            // 방문 안했고, node 노드와 i 노드가 연결되어 있다면 재귀탐색
            if(graph[node][i] && !visited[i]) {
                dfs(i);
            }
        }
    }
    
    // bfs
    static void bfs() {
        queue.addLast(V);
        visited[V] = true;
        sb.append(V+1).append(' ');
        while(!queue.isEmpty()) {
            int node = queue.removeFirst();
            for(int i=0; i<N; i++) {
                // 방문 안했고, node 노드와 i 노드가 연결되어 있다면 큐에 삽입
                if(graph[node][i] && !visited[i]) {
                    visited[i] = true;
                    sb.append(i+1).append(' ');
                    queue.addLast(i);
                }
            }
        }
    }
}

 

 

채점 결과

1260번 채점 결과

기타

• 2차원 배열 말고 리스트를 사용하는 방법도 빨리 기억을 해내야겠다.

 

문제 링크

• 1260번: DFS와 BFS (acmicpc.net)