[백준 25195/ Gold4] YesOrYes - Java(자바)

❓문제 설명

작성자 : 고경호
문제 링크 : https://www.acmicpc.net/problem/25195

 

$N$개의 정점과
$M$개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.

투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다. 투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다. 그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.

투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다. 팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.

오늘도 투어리스트 곰곰이는 음악을 들으면서 여행을 떠나려고 한다. 그러다가 Twice의 노래인 "YES or YES" 에서 다음과 같은 가사를 듣게 된다.

조금 쉽게 말하자면
넌 뭘 골라도 날 만나게 될 거야
Twice, YES or YES 가사 중 일부
투어리스트 곰곰이는 Twice의 노래 가사처럼, 뭘 골라도 팬클럽 곰곰이를 만나게 될 것인지 궁금해졌다.

투어리스트 곰곰이가 어떻게 이동하더라도 팬클럽 곰곰이를 만나게 된다면 "Yes" 를, 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 존재한다면 "yes" 를 출력하자.

❗입출력

[입력]
첫째 줄에는 정점의 개수
$N$과 간선의 개수
$M$이 주어진다. (
$1 \leq N, M \leq 100\,000$)

이후
$M$줄에 걸쳐서 간선의 정보를 나타내는 두 정수
$u$,
$v$ 가 주어진다. 이는 정점
$u$ 에서 정점
$v$ 로 가는 간선이 있음을 의미한다. (
$1 \leq u$,
$v \leq N$,
$u \ne v$)

이후
$M+2$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 개수
$S$ 가 주어진다. (
$1 \leq S \leq N$)

이후
$M+3$번째 줄에는 팬클럽 곰곰이가 존재하는 정점의 번호
$s$ 가 차례대로
$S$개 만큼 주어진다. (
$1 \le s \le N$)

주어진 그래프는 사이클이 없음이 보장된다. 또한 두 정점을 연결하는 간선은 최대 한 개이다.

팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다.

[출력]
문제에서 설명한 조건에 맞춰서 Yes 또는 yes 를 출력한다.

[예시]

🎁 문제 풀이

Map<Integer, Set>를 선언하여 각 지점에 대한 연결노드 정보를 저장한다.
또한 팬이 기다리고 있는 지점에 대한 정보를 Set로 저장한다.
1부터 탐색을 시작하는 go()메서드를 실행한다.
만약 다음 방문할 지점이 팬이 기다리고 있는 지점이라면 방문하지않는다.
더이상 방문할 다음 지점이 없으면 끝지점까지 도달했다고 판단하여 meet = true 지정
meet이 true라면 yes 아니라면 Yes를 출력한다.

🖥️ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static Set<Integer> fanNode = new HashSet<>();
    static Map<Integer, Set<Integer>> map = new HashMap<>();
    static boolean meet = false;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);


        for (int i = 0; i < M; i++){
            input = br.readLine().split(" ");
            int node = Integer.parseInt(input[0]);
            int nextNode = Integer.parseInt(input[1]);

            Set<Integer> set = map.getOrDefault(node, new HashSet<>());
            set.add(nextNode);

            map.put(node, set);
        }

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

        input = br.readLine().split(" ");

        for (String str : input){
            fanNode.add(Integer.parseInt(str));
        }

        if (!fanNode.contains(1)){
            go(map.get(1));
        }

        System.out.println(meet ? "yes" : "Yes");
    }

    public static void go(Set<Integer> set){

        if (set == null || set.isEmpty()){
            meet = true;
            return;
        }

        for (Integer nextNode : set){
            if (!fanNode.contains(nextNode)){
                go(map.get(nextNode));
            }
        }
    }
}