ν•΄λ²„λ‹ˆ 2023. 12. 20. 08:48
λ°˜μ‘ν˜•

 

 

문제

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

 

1260번: DFS와 BFS

첫째 쀄에 μ •μ μ˜ 개수 N(1 ≀ N ≀ 1,000), κ°„μ„ μ˜ 개수 M(1 ≀ M ≀ 10,000), 탐색을 μ‹œμž‘ν•  μ •μ μ˜ 번호 Vκ°€ 주어진닀. λ‹€μŒ M개의 μ€„μ—λŠ” 간선이 μ—°κ²°ν•˜λŠ” 두 μ •μ μ˜ λ²ˆν˜Έκ°€ 주어진닀. μ–΄λ–€ 두 정점 사

www.acmicpc.net

 

 

 

 

 

 

 

 

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static boolean[] visited; // λ°©λ¬Έ μ—¬λΆ€
    public static int[][] graph;
    public static int N; // μ •μ μ˜ 개수 (동그라미)
    public static int M; // κ°„μ„ μ˜ 개수 (직선)
    public static int V; // 탐색 μ‹œμž‘ 번호

    /**
     * 깊이 μš°μ„  탐색
     * 
     * @param v
     */
    public void dfs(int v) {
        visited[v] = true;
        System.out.print(v + " ");

        for (int i = 0; i < N + 1; i++) {
            if (graph[v][i] == 1 && visited[i] == false) {
                dfs(i);
            }
        }
    }

    /**
     * λ„ˆλΉ„ μš°μ„  탐색
     * 
     * @param v
     */
    public void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(v);
        visited[v] = true;

        while (!queue.isEmpty()) {
            int r = queue.poll();
            System.out.print(r + " ");

            for (int i = 1; i < N + 1; i++) {
                if (graph[r][i] == 1 && visited[i] == false) {
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        Main m = new Main();
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        V = Integer.parseInt(st.nextToken());

        graph = new int[N + 1][N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[a][b] = 1;
            graph[b][a] = 1;
        }

        Arrays.fill(visited, false);
        m.dfs(V);
        System.out.println("");

        Arrays.fill(visited, false);
        m.bfs(V);

        bw.flush();
        bw.close();
    }
}

 

 

 

 

 

 

μ •λ‹΅

 

 

 

 

 

 

λ°˜μ‘ν˜•