[DFS] 백준 - 25195번: Yes or yes Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

25195번: Yes or yes

 

 

이번 문제는 길이가 좀 길지만 문제는 간단하다.

곰곰이는 팬들이 있다.

그리고 곰곰이는 간선(양방향 아님)을 통해 팬미팅?을 하는데 투어를 하면서 곰곰이 팬들을 만나지 못하면 yes를

팬들과 만난다면 Yes를 출력하면 된다.

 

Yes인 상황은 예시 그림에서 잘 설명해주었고

yes인 상황은 다음과 같다.

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer>[] map;
    static List<Integer> check;
    static List<Integer> fans;
    static int n;
    static boolean tour;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        int m = sc.nextInt();
        sc.nextLine();

        map = new ArrayList[n];
        check = new ArrayList<>();
        fans = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            map[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            map[a].add(b);
        }

        int temp = sc.nextInt();
        for (int i = 0; i < temp; i++) {
            fans.add(sc.nextInt() - 1);
        }

        dfs(0);

        if (tour) {
            System.out.println("yes");
        } else {
            System.out.println("Yes");
        }
    }

    private static void dfs(int start) {
        if (fans.contains(start)) {
            return;
        }
        if (map[start].isEmpty()) {
            tour = true;
            return;
        }
        check.add(start);

        for (int i = 0; i < map[start].size(); i++) {
            if (!map[map[start].get(i)].isEmpty()) {
                dfs(map[start].get(i));
            } else if (map[map[start].get(i)].isEmpty() && !fans.contains(map[start].get(i))) {
                tour = true;
            }
        }
    }
}

 

dfs 항수에서 보면 

첫 번째 if문은 방문한 노드가 팬 위치 노드에 포함되어있는지

두 번째 if문은 아래와 같은 예제처럼 시작 노드에서 간선이 없을 때 처리이다.

 

 

그리고 for문에서는 map[start]의 사이즈만큼 반복문을 돌면서

만약 map[map[start].get(i)]의 노드가 비어있지 않다면

즉, 간선이 있다면 dfs를 다시 돌리고

 

그렇지 않고 팬 목록에 다음 노드가 포함되어있지 않다면 true 값을 줘서

 

마지막에 팬을 만났는지 안 만났는지에 따라 Yes or yes가 출력된다.