99클럽 코테 스터디 11일차 TIL (25195번: Yes or yes)

문제

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

---

학습키워드

• DFS

 

풀이 및 코드

DFS를 통해 깊게 들어가면서 곰곰이를 만나는지 확인하는 방식이다.

• 정답의 초기값을 "Yes"로 설정한 다음, 탐색 도중 곰곰이를 만난 경우 return을 한다.
• 만약 더 이상 갈 곳이 없는데 곰곰이를 만나지 않았다면 (meet == false)라면 정답을 "yes"로 변경해준다

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

public class Main {

    private static String answer = "Yes";

    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());

       Map<Integer, List<Integer>> graph = new HashMap<>();
       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.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
       }

       int S = Integer.parseInt(br.readLine());
       boolean[] gomgoms = new boolean[N + 1];
       st = new StringTokenizer(br.readLine());
       for (int i = 0; i < S; i++) {
          gomgoms[Integer.parseInt(st.nextToken())] = true;
       }
       dfs(graph, 1, gomgoms, false);
       System.out.println(answer);
    }

    private static void dfs(Map<Integer, List<Integer>> graph, int current, boolean[] gomgoms, boolean meet) {
       if (gomgoms[current]) {
          return;
       }
       if (!graph.containsKey(current)) {
          if (meet == false) {
             answer = "yes";
          }
          return;
       }
       for (int n : graph.get(current)) {
          dfs(graph, n, gomgoms, meet);
       }
    }
}