025 : DFS 친구관계 파악하기

 

 

0번 노드부터 V-1번 노드까지 모두 IS로 보낸다

 

하나라도 체크인되면 나머지는 필요없다. 모든 쌍을 구하는 게 아닌, 존재하느냐의 문제이므로

 

for / while에서 break = DFS와 같은 method에서 return

 

 

 

 

 

pointer와 depth를 사용하여, recursive 시 depth를 보충해 줄 수 있다

 

(pipeline patch)

depth == 5 로 끝내지는 게 아닌 "depth > checkin > break;" signalling 하는 이유는 depth는 DFS안에서 계속 변화하기 때문에 순간을 catch하기 어렵고, 하나의 DFS시작점이 끝나야 for linear 공간은  중 하나가 끝나기 때문이다

 

비보존 patch

- BFS라면 이렇게 해서는 안되지만, DFS 끝에 patch가 들어와 있다면 모든것이 끝난 상황(진입이 다 완료되고 나서 빠져나오면서 모든 visited 정보를 reset한다) 

 

 

 

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

public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] TP;
    static boolean checkin;
    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();

        // D2F
        for (int i = 0; i < V; i++) {
            TP[i] = new ArrayList<>();
        }
        for (int i = 0; i < E; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            TP[s].add(e);
            TP[e].add(s);
        }

        // OP
        visited = new boolean[V+1];
        for (int i = 0; i < V; i++) {
            DFS(i, 1);
            if (checkin)
                break;
        }

        // OEC
        if (checkin)
            System.out.println("1");
        else
            System.out.println("0");
    }

    static void DFS(int now, int depth) {
        if (depth == 5 || checkin) {
            checkin = true;
            return;
        }
        visited[now] = true;
        for (int connected : TP[now]) {
            if (!visited[connected])
                DFS(connected, depth+1);
        }
        visited[now] = false;
    }
}