99클럽 코테 스터디 11일차 TIL

백준 - 25195번

문제 이해

• 사이클이 없는 방향 그래프 -> 단방향 그래프
• 모든 여행 루트 중 어떤 루트로 이동하더라도 만난다면 "Yes"
• 모든 여행 루트 중 팬클럽 곰곰이를 만나지 않는 루트가 있다면 "yes"

구현

DFS를 사용하여 모든 여행 루트를 탐색해야 한다.

여행 루트 탐색 도중 팬클럽 곰곰이를 만난다면, 만나기 전 지점으로 다시 돌아가 새로운 여행 루트를 탐색해야 한다.

팬클럽 곰곰이를 한번도 만나지 않았고, 해당 정점에서 탐색할 루트가 없다면 yes를 출력한다.

귀엽다

예제 입력 1번

위의 그림은 예제 입력 1번의 그림이다.

1번 정점에서 출발하여 2번 루트를 선택했다면 3번과 4번으로 갈 수 있다.

3번과 4번 모두 곰곰이 이슈로 2번 루트에서 빠져나와야 한다.

5번 루트로 이동하려하니 여기도 곰곰이가 있다.

 

6번 정점에서 출발한다면 곰곰이를 만나지 않을 수 있다.

하지만 무조건 1번 정점에서 출발해야되기 때문에 성립될 수 없다.

 

예제 입력 2번

그림과 같이 정점 번호는 같고 다른 것은 3번과 5번 정점에만 곰곰이가 있다.

2번 루트를 선택했을 때 3번에서 return 되고 4번으로 간다면 곰곰이를 만나지 않는 루트에 해당한다.

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

public class Main {

    static ArrayList<Integer>[] graph;
    static int[] fans; // 팬클럽 곰곰이 
    static int unmeetCount = 0; // 곰곰이를 만나지 않은 횟수

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

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

        graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }
        
        // 단방향 그래프
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
        }

        // 곰곰이 투입
        int s = sc.nextInt();
        fans = new int[s];
        for (int i = 0; i < s; i++) {
            fans[i] = sc.nextInt();
        }
        
        // 1번에서부터 출발
        visited[1] = true;
        dfs(1);

        System.out.println(unmeetCount == 0 ? "Yes" : "yes");
        sc.close();
    }

    static void dfs(int node) {
        for (int fan : fans) {
            if (node == fan) {
                return;
            }
        }

        if (graph[node].isEmpty()) {
            unmeetCount++;
            return;
        }

        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next);
            }
        }
    }
}

dfs 함수를 조금 더 살펴보자.

 

1. 정점 번호가 곰곰이가 있는 번호라면 함수를 종료한다.

2. 1번에 해당되지 않고 정점 번호에서 이동할 수 있는 정점이 없다면 만나지 않은 횟수를 증가시키고 함수를 종료한다.

3. 모든 여행 루트를 탐색한다. 

 

위 과정이 반복되고 모든 여행 루트를 탐색했을 때, 곰곰이를 만났다면 unmeetCount = 0일 것이고,

만나지 않았다면 unmeetCount > 0 일 것이다.

개선

dfs 함수 호출마다 매번 순회를 돌리는 부분을 개선하고자 한다.

일반 반복문의 경우  팬클럽 곰곰이의 수가 늘어날수록 시간복잡도가 증가한다.

O(s) - fans 배열에 포함된 요소의 개수에 비례

문제의 마지막 부분에 ' 팬클럽 곰곰이가 존재하는 정점의 번호는 중복해서 주어지지 않는다. ' 라고 쓰여있다.

순서를 보장할 필요가 없고 중복만 허용하지 않는다면 배열대신 HashSet을 사용해볼 수 있을 것 같다.    

 

HashSet

O(1)에 가까운 검색 성능을 가진다.

해시 테이블을 이용해 요소의 해시 값을 기반으로 저장 위치를 결정하므로, 특정 요소를 찾는 속도가 빠르다.

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

public class Main {

    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    static Set<Integer> fanSet; // HashSet 구조로 변경
    static int unmeetCount = 0;

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

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

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            graph[u].add(v);
        }

        int s = sc.nextInt();
        fanSet = new HashSet<>();
        for (int i = 0; i < s; i++) {
            fanSet.add(sc.nextInt());
        }

        visited[1] = true;
        dfs(1);

        System.out.println(count == 0 ? "Yes" : "yes");
        sc.close();
    }

    static void dfs(int node) {
        if (fanSet.contains(node)) return;

        if (graph[node].isEmpty()) {
            unmeetCount++;
            return;
        }

        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next);
            }
        }
    }
}

---

백준 25195번 Yes or yes

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