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

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

 

<초기 아이디어>

주어진 필수 조건은 단방향, 1번에서 출발이다.

DFS로 가다가 방문했던 노드나 팬클럽이 있는 노드가 있으면 지나지 않고 진행한다.

팬클럽 노드를 제외하고 방문했으면 어떻게든 만나지 않고 가는 것이니 yes, 아니면 Yes를 출력한다

-> 그리고 이를 '팬클럽노드 수 s + 방문한 노드 수 = 총 노드 수' 라고 조건 걸었다

하지만 이렇게 하니 예제를 넣었을 때 출력 값이 틀리게 나왔다.

주어진 본문 예제가 아닌 예제 2번을 만족하지 않았다.

 

<문제>

예제 2번을 해석해보니 '여행이 끝났다' 라는 말이 해당 노드에서 이동할 수 있는 노드가 없는 경우 라는 것을 깨달았다.

양방향이 아닌 단방향 노드이니 당연히 모든 노드를 방문했을 때 여행이 끝나는 것이 아니었다

그래서 DFS에 아래의 추가 조건을 걸었다.

if(list[x].isEmpty()) flag = true;

 

<최종 아이디어>

1. 단방향 간선 입력, 팬클럽 노드는 visited 방문처리, 1번에서 출발

2. DFS로 탐색하다가 더 이상 나갈 수 없는 노드가 없으면 (=여행이 끝나면) flag = true;

3. 방문했거나 팬클럽 있는 노드 (vistied = true) 면 continue;

4. flag = true면 만나지 않는 방법이 존재한 것이니 yes 출력, 그렇지 않으면 Yes 출력

 

<제출 코드>

package STUDY.Week02;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Day11_BOJ_25195_Yesoryes {

    static int n, m;
    static boolean flag;
    static List<Integer>[] list;
    static boolean[] visited;

    public static void dfs(int x){
        visited[x] = true;
        if(list[x].isEmpty()) flag = true;	// 노드의 끝 도착한 경우 (단방향으로 나가는 노드 없음)
        for(int i=0; i<list[x].size(); i++){
            int now = list[x].get(i);
            if(visited[now]) continue;		// 방문했던 노드나 팬클럽 있는 노드 제외
            dfs(now);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        list = new ArrayList[n+1];
        for(int i=0; i<n+1; i++) list[i] = new ArrayList<>();
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            list[x].add(y);
        }
        visited = new boolean[n+1];
        int s = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<s; i++){
            int idx = Integer.parseInt(st.nextToken());
            visited[idx] = true;	// 팬클럽 노드는 아예 방문처리(안갈꺼니까)
        }
        if(!visited[1]) dfs(1);		// 1번노드부터 팬클럽있으면 건너뜀
        if(flag) System.out.println("yes");
        else System.out.println("Yes");
    }
}