[자바] 백준 25195 - YES or yes (boj java)

문제 : boj25195

 

  그래프 탐색에 대해 단순하게 DFS, BFS만 익힌게 아니고 이해하고 있다면 사실 엄청 쉬운 문제이다. 결국 DFS(깊이 우선 탐색)으로 진행하면서 팬을 만나지 않고 더이상 진행할 간선이 없는 곳에 도착하는지만 보면 된다. 주의할 점은 방문체크를 두면 안된다. 왜냐면 이미 팬을 만난채로 진행한 경로라서 방문체크가 됬더라도 팬을 만나지 않은채로 진행이 가능해야 하기 때문이다. 이럼 사실 방문체크를 하되, 팬을 만나고 도착했는지 팬을 안만나고 도착했는지에 따라 dp를 좀 끼얹어서 그래프 탐색을 해도 되긴한다.

 

  근데 어차피 DAG(Directed Acyclic Graph. 사이클 없는 방향그래프)이므로 팬을 만났다면 바로 back tracking으로 이전으로 돌아가기만 해도 된다. 이 경우 1차원 방문체크로도 충분하다. 근데 어차피 방향성이 있고, 팬을 만나면 되돌아온다면 애초에 방문체크를 할 이유가 없다. 하던 안하던 동일하게 진행되기 때문이다. 아무튼 그러니까 위의 로직대로 그래프 탐색을 하다가 진행할 간선이 0인 곳을 만난다면 "YES"이다. 그런 경우가 없었다면 "yes"이다.

 

코드 : github

...
HashSet<Integer> fan;
ArrayList<Integer>[] edges;
boolean chk = false;
private void dfs(int cur) {
    if (chk || fan.contains(cur)) return;
    if (edges[cur].size() == 0) {
        chk = true;
        return;
    }
    for (Integer next : edges[cur]) dfs(next);
}
private void solution() throws Exception {
    int n = nextInt();
    int m = nextInt();
    edges = new ArrayList[n+1];
    for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
    while (m-->0) edges[nextInt()].add(nextInt());
    int s = nextInt();
    fan = new HashSet<>();
    while (s-->0) fan.add(nextInt());
    dfs(1);
    System.out.println(chk?"yes":"Yes");
}
...