[Day11]JAVA- 백준 Yes or yes (25195번) DFS,BFS 활용

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

 

25195번 문제는 BFS , DFS 둘다 활용해서 풀 수 있다.

 

https://h0wever.tistory.com/6

[알고리즘] DFS (깊이 우선 탐색) 이해

 

주의해야 하는 것은 단방향이고 , 팬클럽 곰곰이를 만나지 않고 이동하는 방법이 하나라도 존재한다면 "yes" 이다.

 

DFS 방식을 이용한다면 4가지 경우를 고려해야한다. 

1.  처음 1 정점에 곰곰이 팬들이 있는 경우 -> 그 다음 어디로 가던 이미 팬을 마주친거라 바로 끝
2.  처음 1 정점에 연결된 다른 정점이 없는 경우 -> 더 이상 갈 곳이 없으므로 끝
3.  여행을 가던 중 곰곰이 팬이랑 마주치면 -> 그 길을 더이상 가지 않고 무시
4.  여행을 가던 중(팬을 마주치지 않고) 더이상 연결된 간선이 없을 경우-> yes 완료

 

재귀함수를 사용하여서 팬을 만나지 않은 경로를 찾을때까지 함수를 호출 하는 것이다. 

만났으면 meet = true  만나지 않고 길이 끝나면 meet = false ,

재귀 호출도 끝

public static void  DFS(int v)
{ 
    if(fans.contains(v))
    {                            
        //처음 1 정점에 곰곰이 팬이랑 마주친다면 끝
        return;                                                 
    }

    else if(graph.get(v).isEmpty())
    {
        //처음 1 정점에 연결된 다음 정점이 없는 경우 끝 
        meet = false;   
        return;
    } 

    for(int g : graph.get(v))
    {
        if(fans.contains(g))
        {                            
            //곰곰이 팬이랑 마주친다면 그 길은 더 이상 가지 않고 무시
            continue;                                            
        }
        else if(graph.get(g).isEmpty())
        {
            //더이상 다음 정점이 없는 경우 끝             
            meet = false;                         
            return;
        }    
        else
        {
            //다음 정점으로 이동
            DFS(g);
        }      
    }  
}

 

 

BFS 방식도 팬을 만나지 않은 경로를 찾을때까지 while문을 도는 것이다. 

대신 Queue 를 사용하여서 팬을 만나지 않은 경로를 Queue에 넣는다.

1.  팬을 마주치는 정점은 더 이상 가지 않고 무시 
2.  팬도 마주치지 않고 연결된 간선도 있으면 다음 정점으로 이동한다. 
3.  여행을 가던 중(팬을 마주치지 않고) 더이상 연결된 간선이 없을 경우-> yes 완료

 public static void BFS(int v)
{
    Queue<Integer> que = new LinkedList<>();

    //처음 정점 que에 넣기
    que.add(v);
    visited[v] = true;

    while(!que.isEmpty())
    {
        int now = que.poll();

        //곰곰이 팬이랑 마주친다면 그 길은 더 이상 가지 않고 무시
        if(fans.contains(now))
            continue;

        //더이상 다음 정점이 없는 경우 끝            
        if(graph.get(now).isEmpty())
        {
            meet =false;
            return;
        }
        else
        {   
            for(int g : graph.get(now))
            {
                if(!visited[g])
                {
                    que.add(g);
                    visited[g] = true;
                }
            }
        }
    }
}

 

*최종코드 

//25195번 
import java.util.*;
import java.io.*;
public class Main{     
    static int N; //정점
    static int M ;//간선
    static int fanCnt; //팬클럽 곰곰이들
    static ArrayList<Integer> fans = new ArrayList<>(); //팬들이 있는 정점
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>(); 
    static Boolean meet = true;    
    static Boolean visited[];

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

        visited = new Boolean[N+1];

        //노드 초기화
        for(int i=0;i<=N;i++)
        {
            graph.add(new ArrayList<>());
            visited[i] = false;
        }

        //간선 추가
        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);//단방향
        }

        //팬클럽 곰곰이 수 
        fanCnt = Integer.parseInt(br.readLine());

        //팬클럼 곰곰이들이 있는 정점
        st = new StringTokenizer(br.readLine(), " ");
        for(int i=0;i<fanCnt;i++)
        {            
            fans.add(Integer.parseInt(st.nextToken()));
        }
       
        //시작은 1
        BFS(1);

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

    public static void  DFS(int v)
    { 

        if(fans.contains(v))
        {                            
            //처음 1 정점에 곰곰이 팬이랑 마주친다면 끝
            return;                                                 
        }

        else if(graph.get(v).isEmpty())
        {
            //처음 1 정점에 연결된 다음 정점이 없는 경우 끝 
            meet = false;   
            return;
        } 

        for(int g : graph.get(v))
        {
            if(fans.contains(g))
            {                            
                //곰곰이 팬이랑 마주친다면 그 길은 더 이상 가지 않고 무시
                continue;                                            
            }
            else if(graph.get(g).isEmpty())
            {
                //더이상 다음 정점이 없는 경우 끝             
                meet = false;                         
                return;
            }    
            else
            {
                //다음 정점으로 이동
                DFS(g);
            }      
        }  
    }

    public static void BFS(int v)
    {
        Queue<Integer> que = new LinkedList<>();
        
        //처음 정점 que에 넣기
        que.add(v);
        visited[v] = true;

        while(!que.isEmpty())
        {
            int now = que.poll();

            //곰곰이 팬이랑 마주친다면 그 길은 더 이상 가지 않고 무시
            if(fans.contains(now))
                continue;

            //더이상 다음 정점이 없는 경우 끝            
            if(graph.get(now).isEmpty())
            {
                meet =false;
                return;
            }
            else
            {   
                for(int g : graph.get(now))
                {
                    if(!visited[g])
                    {
                        que.add(g);
                        visited[g] = true;
                    }
                }
            }
        }
    }
}