[백준] 5848 Message Relay - Graph Theory / Java

• 문제 링크

5848번: Message Relay

 

• 풀이 과정

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    static int[] graph;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        graph = new int[n];
        for (int i = 0; i < n; i++)
            graph[i] = Integer.parseInt(br.readLine()) - 1;

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            visit = new boolean[n];
            if (!dfs(i)) cnt++;
        }

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

    private static boolean dfs(int node) {
        if (graph[node] == -1) return false;

        if (visit[node]) return true;
        visit[node] = true;

        return dfs(graph[node]);
    }

}

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Main {

    static int[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        graph = new int[n];
        for (int i = 0; i < n; i++)
            graph[i] = Integer.parseInt(br.readLine()) - 1;

        int cnt = 0;
        while (n-- > 0) if (!bfs(n)) cnt++;

        bw.write(String.valueOf(cnt));
        bw.flush();
    }

    private static boolean bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();

        q.offer(node);
        set.add(node);

        while (!q.isEmpty()) {
            int tgt = graph[q.poll()];

            if (set.contains(tgt)) return true;
            if (tgt == -1) return false;

            q.offer(tgt);
            set.add(tgt);
        }

        return false;
    }

}