[소프티어] 6248번 - 출퇴근길 [Java]

https://softeer.ai/practice/6248

 

[소프티어] 6248번 - 출퇴근길 [Java]

[소프티어] 6248번 - 출퇴근길 [Java]

[소프티어] 6248번 - 출퇴근길 [Java]

[소프티어] 6248번 - 출퇴근길 [Java]

[소프티어] 6248번 - 출퇴근길 [Java]

---

1.  아이디어

 

시작점에서 방문할 수 있는 점들은 DFS 알고리즘으로 간단하게 구할 수 있다. 이때 다른 점들에서 도착점을 갈 수 있는지 여부는 역방향 간선을 활용해서 도착점에서 역방향 간선으로 DFS 알고리즘을 적용하면 간단하게 구할 수 있다.

---

2. 문제풀이

 

동환이의 집에서 출근길에 포함되는 점들은 동환이의 집에서 DFS 알고리즘으로 방문 가능한 정점을 찾고 다시 방문 가능한 점들이 회사에 갈 수 있는지 찾으면 구할 수 있다. 하지만 처음 동환이가 찾은 방문 가능한 정점의 수가 늘어날 수록 DFS 알고리즘을 반복적으로 적용해야해서 시간초과가 발생하게 된다. 이를 해결하기 위해 동환이의 집에서 출근길에 포함되는 점들을 DFS 알고리즘으로 찾은 후 회사에서 역방향 간선으로 방문 가능한 정점을 찾았다. 역방향 간선을 활용하면 도착점에서 방문 가능한 점들은 정방향 간선에서 해당 위치를 시작점으로 도착점에 갈 수 있는 점들만 찾게 된다. 이 두 정점들 중 겹치는 정점들이 출근경로에 포함되는 점들이고 이를 Set의 retainAll 메서드로 교집합을 구하는 방식으로 구했다. 퇴근길도 똑같이 반복해주면 된다.

주의할 점은 출근길에서 회사는 한번만 도착할 수 있어서 회사를 발견하면 해당 위치에서 DFS를 지속하면 안되고 역방향 탐색은 집을 발견했을 때 DFS를 멈추면 안된다.

---

3. 코드

 

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

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

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

        List<List<Integer>> adj = new ArrayList<>();
        List<List<Integer>> adjReverse = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
            adjReverse.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());
            adj.get(u).add(v);
            adjReverse.get(v).add(u);
        }

        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int T = Integer.parseInt(st.nextToken());

        Set<Integer> sTotSet = new HashSet<>();  // S에서 갈 수 있는 모든 점을 담은 Set(T를 만나면 종료)
        Set<Integer> tToAllSet = new HashSet<>();  // T에서 갈 수 있는 모든 점을 담은 Set
        Set<Integer> tTosSet = new HashSet<>();  // T에서 갈 수 있는 모든 점을 담은 Set(S를 만나면 종료)
        Set<Integer> sToAllSet = new HashSet<>();  // S에서 갈 수 있는 모든 점을 담은 Set

        dfs(S, T, adj, sTotSet);
        dfs(T, 0, adjReverse, tToAllSet);
        dfs(T, S, adj, tTosSet);
        dfs(S, 0, adjReverse, sToAllSet);

        sTotSet.retainAll(tToAllSet);  // sTotSet과 tToAllSet의 교집합은 출근길 경로에 포함되는 점
        tTosSet.retainAll(sToAllSet);  // tTosSet과 sToAllSet의 교집합은 퇴근길 경로에 포함되는 점

        sTotSet.retainAll(tTosSet);  // sTotSet과 tTosSet의 교집합은 출퇴근길 경로에 포함되는 점

        System.out.println(sTotSet.size());
    }

    private static void dfs(int node, int target, List<List<Integer>> adj, Set<Integer> visited) {
        if (node == target) return;

        visited.add(node);

        for (int next : adj.get(node)) {
            if (visited.contains(next)) continue;

            dfs(next, target, adj, visited);
        }
    }

}

---

4. 후기