1260번: DFS & BFS (실버 2)

1260번: DFS와 BFS (acmicpc.net)

1260번: DFS와 BFS

1. 문제 설명

 

 

 

 

2. 입출력 조건 및 예제

입력 조건

(1) 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 

(2) 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다.

(3) 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있으며, 입력으로 주어지는 간선은 양방향이다.

 

출력 조건

(1) 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. 

( V부터 방문된 점을 순서대로 출력하면 된다. )

 

입출력 예제

 

 

 

3. 풀이 및 코드

: 두 문제에 대한 풀이는 이미 아래의 링크에서 설명하였기 때문에 여기서는 생략하겠다.

DFS (Depth First Search) (tistory.com)

BFS (Breadth First Search) (tistory.com)

 

( 단, DFS, BFS 모두 인접 행렬로 풀었다. )

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int N, M, V;
    static int[][] graph = new int[1001][1001];
    static boolean[] visited = new boolean[1001];
    static Queue<Integer> q = new LinkedList<>();
    
    static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(sc.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());
        
        for(int i=1; i<=M; i++) {
            st = new StringTokenizer(sc.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            // 양방향이므로
            graph[a][b] = 1;
            graph[b][a] = 1;
        }
        dfs(V);
        sb.append("\n");
        visited = new boolean[1001];
        
        bfs(V);
        System.out.println(sb);
    }
    
    static void dfs(int nodeIndex) {
        visited[nodeIndex] = true;
        
        sb.append(nodeIndex + " ");
        
        for(int i=1; i<=N; i++) {
            if(graph[nodeIndex][i] == 1 && !visited[i]) {
                dfs(i);
            }
        }
    }
    
    static void bfs(int nodeIndex) {
        q.add(nodeIndex);
        visited[nodeIndex] = true;
        
        while(!q.isEmpty()) {
            nodeIndex = q.poll();
            sb.append(nodeIndex + " ");
            
            for(int i=1; i<=N; i++) {
                if(graph[nodeIndex][i] == 1 && !visited[i]) {
                    q.add(i);
                    visited[i] = true;
                }
            }
        }
    }
}