[Softeer] [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길 -Java

문제 링크

이전 글에서 레벨3인데 쉽다했더니 바로 어려운 문제를 맞닥뜨렸다. 길찾기라는걸 봐서는 대충 DFS나 BFS를 활용해서 풀면 되겠거니 싶었다. 그래서 처음에는 S에서 T로 가는 길, T에서 S로 가는 길을 구해서 겹치는 것들을 모두 구하면 되지 않을까 싶었다. 구현을 어떻게 할지 감이 안잡혀서 다른 사람들의 풀이를 찾아보았는데, 나처럼 생각하고 코드를 짰는데 틀렸다는 사람이 있었다(참고). 여기에 왜 안되는지 반례가 잘 정리되어 있다.

그리고 위 블로그에서 힌트를 얻을 수 있었다.

1. <출근길> S에서 T까지 순방향 그래프(문제에서 주어진 단방향 그래프)에서 DFS를 돌아서 방문한 노드들을 저장한다.
2. <출근길> 역방향 그래프(주어진 단방향 그래프의 방향을 반대로)에서 T에서 연결된 모든 노드를 방문할 때 까지 DFS를 돌면서 방문한 노드를 저장한다.
3. <퇴근길> T에서 S까지 순방향 그래프(문제에서 주어진 단방향 그래프)에서 DFS를 돌아서 방문한 노드들을 저장한다.
4. <퇴근길> 역방향 그래프(주어진 단방향 그래프의 방향을 반대로)에서 S에서 연결된 모든 노드를 방문할 때 까지 DFS를 돌면서 방문한 노드를 저장한다.
5. 위 과정에서 각각 저장한 노드들의 교집합을 찾는다.
6. S와 T를 제외한 중간 지점들의 개수만 구하는것이니 교집합 결과에서 -2를 한다.

2번, 4번 과정을 진행하는 이유
중간에 있는 노드들이 T까지 연결되어 있는지 확인하기 위해서이다. 1번과 3번 과정을 통해 출근길과 퇴근길에 방문할 수 있는 모든 노드를 구한 후 각 노드에 대해서 DFS를 수행하여 T까지 연결되어있는지 확인한다면 시간초과가 나게 될 것이다.

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

public class sol363 {
    static int n;
    static int m;
    static List<List<Integer>> graph;
    static List<List<Integer>> rGraph;
    static int S;
    static int T;

    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());

        graph = new ArrayList<>();
        rGraph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
            rGraph.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);
            rGraph.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<>();
        dfs(S, T, s1, graph, new boolean[n + 1]);
        dfs(T, -1, s2, rGraph, new boolean[n + 1]);
        s1.retainAll(s2);

        Set<Integer> s3 = new HashSet<>();
        Set<Integer> s4 = new HashSet<>();
        dfs(T, S, s3, graph, new boolean[n + 1]);
        dfs(S, -1, s4, rGraph, new boolean[n + 1]);
        s3.retainAll(s4);

        s1.retainAll(s3);

        int result = s1.size();
        if (s1.contains(S)) {
            result--;
        }
        if (s1.contains(T)) {
            result--;
        }
        System.out.println(result);

    }

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

        for (int i = 0; i < graph.get(node).size(); i++) {
            int next = graph.get(node).get(i);
            if (visited[next]) {
                continue;
            }
            visited[next] = true;
            set.add(next);
            dfs(next, target, set, graph, visited);
        }

    }
}

참고 블로그
참고 해설 영상