TIL(Today I Learned)

[TIL] 99클럽 코테 스터디 11일차 TIL + 백준 25195 Yes or yes

zincah 2024. 11. 8. 00:22
반응형

 

문제 풀이

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

 

문제 탐색하기

알고리즘 파악하기

곰곰이는 단방향 간선을 따라 이동하는데 이동하지 못하게 되었을 때 투어가 끝난다고 합니다. 투어가 끝나는 경우는 여러가지가 있을 텐데 그 중에서 곰곰이의 팬을 한번도 만나지 않고 투어가 끝났을때가 있는지 판단하면 됩니다.

따라서 깊이 우선 탐색 (DFS)을 사용하면 곰곰이의 투어를 하나하나 탐색할 수 있습니다. 

 

재귀호출을 통해서 구현하였는데 다음노드로 넘어가게 되었을 때 곰곰이의 팬이 노드에 존재한다면 "yes" 문자열을 "Yes" 로 변경해줍니다. 재귀호출이 종료되면 다시 탐색을 시작했던 노드로 돌아가게 되는데 이때 돌아간 노드에서의 팬을 만났는지 판단하는 문자열로 리셋해줍니다. 

 

이렇게 탐색을 반복하다가 탐색할 수 있는 노드가 더이상 없고 문자열이 "yes" 로 저장되어있다면 팬을 만나지 않고 투어가 종료됬다는 뜻이므로 답을 "yes"로 출력하고 이 조건에 걸리지않는다면 모든 투어에 팬을 만났다는 뜻이므로 "Yes"가 답이 됩니다.

 

고려해야할 점

  • 1번 노드에 팬이 존재할 경우에는 팬을 무조건 만난다는 뜻이라는 것을 고려해야 합니다.
  • 이 문제에서는 방문한 노드여도 다시 방문할 수 있기때문에 방문 여부를 체크하지 않습니다.

 

문제 풀이

package backjun;

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

public class Boj25195 {

    static ArrayList<ArrayList> graph = new ArrayList<>();
    static int[] pan;
    static String result = "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());

        for(int i=0; i<=N; i++){
            graph.add(new ArrayList());
        }

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

        for(int i=1; i<=N; i++){
            Collections.sort(graph.get(i));
        }

        int S = Integer.parseInt(br.readLine());
        pan = new int[S];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<S; i++){
            pan[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(pan);

        if(pan[0] == 1){
            System.out.println("Yes");
        }else{
            dfs(1, "yes");
            System.out.println(result);
        }
    }

    private static void dfs(int start, String meet){
        String meetSave = meet;

        if(graph.get(start).size() == 0 && meet.equals("yes")){
            result = meet;
        }

        for(int i=0; i<graph.get(start).size(); i++){
            meet = meetSave;

            int x = (int)graph.get(start).get(i);
            for(int j=0; j<pan.length; j++){
                if(pan[j]==x){
                    meet = "Yes";
                    break;
                }
            }
            dfs(x, meet);
        }
    }


}

 

 

오늘의 회고

bfs로 풀어야하는 건가 dfs로 풀어야하는 건가 고민하다가 처음에는 bfs로 풀었습니다. 도중에 각이 안나오는 것을 깨닫고 dfs로 돌려서 풀었는데 이 과정에서 시간을 많이 소비했습니다,, 문제를 훑어보면서 과연 어떤 알고리즘으로 풀면 빠르게 답을 구할 수 있을지에 대한 연습을 많이 해야할 것 같습니다ㅎㅎ 그래도 오늘은 지금까지 공부했던 dfs, bfs알고리즘을 바탕으로 답을 구해낼 수 있어서 보람찬 하루였습니다!

반응형