[소프티어] 출퇴근길

https://softeer.ai/practice/6248

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

 

그래프 알고리즘에 DFS 알고리즘을 사용하면 될 것이라고 생각했고, 제약조건이 N <= 100,000, M <= 200,000 이기 때문에  시간복잡도 O(N + M)으로 충분히 효율적인 풀이 방법이라 생각했다.

 

하지만 그래프 구현까지만 가능했고, dfs를 통해 어떻게 방문을 했는지 헤매게 되어 결국 정답을 보았다.

 

검색한 코드

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

public class Main {
    private static int N,M,S,T;
    private static List<List<Integer>> graph = new ArrayList<>();
    private static List<List<Integer>> reverseGraph = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 그래프 초기화
        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 firstNode = Integer.parseInt(st.nextToken()) - 1;
            int secondNode = Integer.parseInt(st.nextToken()) - 1;

            graph.get(firstNode).add(secondNode);
            reverseGraph.get(secondNode).add(firstNode);
        }

        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken()) - 1;
        T = Integer.parseInt(st.nextToken()) - 1;
        
        System.out.println(getResult());
    }
    
    private static int getResult() {
        // 출근길
        boolean[] v1 = new boolean[N];
        v1[T] = true;
        dfs(S, graph, v1);

        boolean[] v2 = new boolean[N];
        dfs(T, reverseGraph, v2);

        // 퇴근길
        boolean[] v3 = new boolean[N];
        v3[S] = true;
        dfs(T, graph, v3);

        boolean[] v4 = new boolean[N];
        dfs(S, reverseGraph, v4);

        int ans = 0;
        for (int i=0; i<N; i++) {
            if (v1[i] && v2[i] && v3[i] && v4[i]) ans++;
        }

        // S와 T 노드를 제외해야 하기 때문에 -2 함
        return ans-2;
    }

    private static void dfs(int current, List<List<Integer>> graph, boolean[] v) {
        if(v[current]) return;
        
        v[current] = true;
        for (int next : graph.get(current)) {           
            dfs(next, graph, v);
        }   
    }
}

 

출퇴근 기준으로 방문했는지를 표시하는 boolean 타입 배열 4개를 사용하는 방식이 인상적이였다.