[백준] 25195번 Java (그래프, dfs, bfs)

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

문제

풀이

접근법 : bfs와 dfs로 풀 수 있는 문제다.
경로를 탐색하면서 팬을 만나거나, 정점에 도달할 수 없다면 Yes, 팬을 만나지 않고 도달할 수 있다면 yes를 출력한다.

dfs로 푸는 경우

static void dfs(int current){
        // 팬이 있는 곳을 지나간 경우
        if(check || fans.contains(current)) return;
        // 가져올 간선이 없다면
        if(graph.get(current).isEmpty()){
            check = true;
            return;
        }
        for(int next : graph.get(current)) dfs(next);
  }

• 가져올 다음 간선이 없을 때까지 탐색한다.
• 만약 팬을 만나면 탐색을 종료한다.
• 간선이 없는 노드에 도달하면 경로가 존재함을 표시한다.
• 방문체크를 하지 않아도 문제가 없다. (참고한 블로그)

bfs로 푸는 경우

static void bfs(int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        boolean[] visited = new boolean[graph.size()];
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            
            if (fans.contains(current)) continue;
            if (graph.get(current).isEmpty()) {
                check = true;
                return;
            }
            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }

• 큐에 넣어서 탐색한다.
• 팬을 만나면 바로 건너뛴다.
• 가져올 다음 간선이 없다면 경로가 존재함을 표시한다.
• 방문한 노드를 다시 탐색하지 않도록 표시한다.

내 코드

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

public class Main {
    static List<List<Integer>> graph;
    static Set<Integer> fans = new HashSet<>(); // 팬이 있는 정점
    static boolean check = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            graph.get(u).add(v);
        }
        
        int s = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < s; i++) {
            fans.add(Integer.parseInt(st.nextToken()));
        }
        
        dfs(1);
        System.out.println(check ? "yes" : "Yes");
    }
    
  static void dfs(int current){
        // 팬이 있는 곳을 지나간 경우
        if(check || fans.contains(current)) return;
        // 가져올 간선이 없다면
        if(graph.get(current).isEmpty()){
            check = true;
            return;
        }
        for(int next : graph.get(current)) dfs(next);
  }
  
  static void bfs(int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        boolean[] visited = new boolean[graph.size()];
        visited[start] = true;
        
        while (!queue.isEmpty()) {
            int current = queue.poll();
            if (fans.contains(current)) continue;
            if (graph.get(current).isEmpty()) {
                check = true;
                return;
            }
            
            for (int next : graph.get(current)) {
                if (!visited[next]) {
                    queue.add(next);
                    visited[next] = true;
                }
            }
        }
    }
}