[sof] 소프티어 <인증평가(6차) 기출> 출퇴근길 - DFS

[문제]

https://softeer.ai/practice/result.do?eventIdx=1&submissionSn=SW_PRBL_SBMS_174270&psProblemId=1529 

https://softeer.ai/practice/result.do?eventIdx=1&psProblemId=1529&submissionSn=SW_PRBL_SBMS_174270

 

[풀이]

이 문제의 핵심은 역방향 간선 그래프를 이용하는 것이다.

출근길과 퇴근길에 모두 포함될 수 있는 정점을 구해야 한다. 이를 위해 집 s를 시작점으로 dfs를 한 번 돌리면 s와 연결되어있는 모든 정점을 구할 수 있다. 주의할 점은 출근길 경로에 회사 t는 한번만 등장한다. 즉 t에 도달하면 dfs를 멈춘다.

이제 s와 연결되어있는 모든 중간 노드에 대해 dfs를 돌려서 회사 t에 도달할 수 있는지 확인해볼 수 있다. 그러나 최악의 경우 중간 노드가 n-2개가 될 수 있기 때문에 시간 복잡도가 O(n(n+m))이 된다. n이 최대 10^5이므로 10^10이 되어 시간초과가 발생할 것이다.

이 문제를 해결하기 위해 역방향 간선 그래프를 이용할 수 있다! 역방향 간선 그래프에 대해서 t가 도달할 수 있는 모든 정점을 dfs를 돌려 저장해준다. 역방향 간선 그래프에서 t가 어떤 정점에 도달할 수 있다는 것은 정방향 간선 그래프에서 그 정점이 t에 도달할 수 있음을 의미한다.

같은 방식으로 t를 시작점으로 한 퇴근길 경로에 대한 dfs, 역방향 간선 그래프에서 s가 도달할 수 있는 정점을 구하는 dfs를 돌린다.

이후 retainAll()을 통해 교집합을 구하면 총 4번의 dfs를 돌려서 답을 구할 수 있다. 시간복잡도는 O(n+m)으로 해결 가능하다.

 

[코드]

 

import java.io.*;
import java.util.*;

public class Main{
    static int n, m;
    static int s, t;
    static List<List<Integer>> graph;
    static List<List<Integer>> reverseGraph;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        graph = new ArrayList<>();
        reverseGraph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
            reverseGraph.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);
            reverseGraph.get(v).add(u);
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());

        Set<Integer> s1 = new HashSet<>();
        Set<Integer> s2 = new HashSet<>();
        //s에서 도달할 수 있는 중간 정점들 
        dfs(s, t, graph, s1, new boolean[n+1]);
        //역방향 간선에 대해서 t에서 도달할 수 있는 정점 -> s->t에서 도달가능한 정점
        dfs(t, -1, reverseGraph, s2, new boolean[n+1]);

        s1.retainAll(s2); //교집합

        Set<Integer> s3 = new HashSet<>();
        Set<Integer> s4 = new HashSet<>();
        //t에서 도달할 수 있는 정점들
        dfs(t, s, graph, s3, new boolean[n+1]);
        //역방향 간선에 대해서 s에서 도달할 수 있는 정점들 
        dfs(s, -1, reverseGraph, s4, new boolean[n+1]);

        s3.retainAll(s4);

        s1.retainAll(s3);
        
        int answer = s1.size();

        if(s1.contains(s)) answer--;
        if(s1.contains(t)) answer--;

        System.out.println(answer);
    }

    public static void dfs(int node, int stop, List<List<Integer>> graph, Set<Integer> set, boolean[] visited){
        if(stop!=-1 && node==stop){
            return;
        }

        for(int i=0; i<graph.get(node).size(); i++){
            int next = graph.get(node).get(i);

            if(visited[next]) continue;

            visited[node] = true;
            set.add(next);
            dfs(next, stop, graph, set, visited);
        }

        return;

    }
}