[소프티어] 출퇴근길

자동차로 출퇴근을 하는 동환이는 지루하지 않게 종종 길을 바꿔 다니곤 한다. 새로운 동네를 발견하는 일은 동환이의 소소한 행복이다.

동환이의 출근길과 퇴근길은 가끔 겹친다. 즉, 출근길에 들른 동네를 퇴근길에 다시 지나곤 하는 것이다. 이에 대해 곰곰이 생각하던 동환이는 이렇게 두 번 들를 수 있는 동네가 그렇게 많지 않음을 깨달았다. 도로의 연결 모양, 그리고 일방통행 여부 등으로 인해 출퇴근길 모두 방문 가능한 동네가 한정되는 것이다.

동환이의 출퇴근길은 단방향 그래프로 나타낼 수 있다. 즉, 각 동네를 1부터 n까지의 번호가 매겨진 n개의 정점으로, m개의 일방통행의 도로를 단방향 간선으로 삼아 그래프를 만들 수 있다. 이때 동환이의 집과 회사가 각각 정점 S와 T로 나타난다고 하면 출퇴근길은 S와 T 사이의 경로로 나타난다.

동환이의 출퇴근길을 본딴 그래프가 주어지면 S에서 T로 가는 출근길 경로와 T에서 S로 가는 퇴근길 경로에 모두 포함될 수 있는 정점의 개수를 세는 프로그램을 작성하시오.

단, 출퇴근길에서 목적지 정점을 방문하고 나면 동환이는 더 이상 움직이지 않는다. 즉, 출근길 경로에 T는 마지막에 정확히 한 번만 등장하며, 퇴근길 경로도 마찬가지로 S는 마지막에 한 번만 등장해야 한다. (출근길 경로에 S는 여러 번 등장해도 되고, 퇴근길 경로에 T는 여러 번 등장해도 된다.)

제약조건
* 5 ≤ n ≤ 100,000
* 5 ≤ m ≤ 200,000
* 1 ≤ S ≤ n이고 1 ≤ T ≤ n이며 S ≠ T
* S에서 T로 가는 경로와 T에서 S로 가는 경로가 하나 이상 존재함이 보장된다.
* 간선의 양 끝 점은 서로 다르다.
* 같은 정점쌍을 같은 방향으로 잇는 간선은 두 개 이상 주어지지 않는다.

출퇴근길

이번 문제는 출퇴근길에 모두 방문할 수 있는 정점을 찾는 문제였다.

간단하게 dfs()를 통해서 s->t, t->s 로의 탐색을 통해 방문할 수 있는 정점의 교집합을 찾으면 될 줄 알았다.

하지만 여기서 예시를 들어보자.
출근길, 퇴근길 모두 방문 가능한 정점은 4 이다.

하지만, 처음 생각한 방법으로 접근한다면 S(시작점) 1로부터 4로 방문하는 1번 방법을 모색하고,
T(도착점) 3으로부터 4를 방문하는 3번 방법을 탐색하게 될 것이다.

즉, 2번, 4번 방법을 추가적으로 탐색해서 1~4 번의 교집합 을 찾아야 한다.
(조금만 생각해봐도 1, 3 번 만 탐색하는 걸로는 반례가 생길 수 밖에 없게된다.)

여기서 2번, 4번 을 쉽게 구할 수 있게 해주는 것이 역방향 그래프 이다.
역방향 그래프는 간단하게 기존 그래프에서 간선의 방향이 반대인 그래프이며, 그렇기에 역방향 그래프에서 1번 3번 방향으로 진행하는 것이 곧 2번, 4번 에 해당하는 꼴이 된다.

또한, 생각해야 될 점은

현재는 출근길에서 1 4 3 5 1 4 3 이 가능하다. 즉, 도착점에 도착했어도 멈추지 않기에 5번 정점 또한 가능하다고 판단하게 된다.
그렇기에 출근길에서는 도착 정점을 미리 방문표시 해주고, 퇴근길에서는 시작 정점을 미리 방문표시해주면 된다.

코드

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

/*
4초, 1024MB
---
출근길과 퇴근길 모두에서 방문 가능한 정점의 개수 구하기
출퇴근길은 단방향 그래프

s -> t, t -> s dfs() 를 진행해서 같은 것을 찾으면 될까? - 불가능

그렇기에 역방향 그래프 라는 개념을 사용해야 함.
- ( S )에서 도달 가능한 정점
- ( T )에서 도달 가능한 정점
- ( S )로 들어올 수 있는 정점
- ( T )로부터 도달 가능한 정점
---
n <= 100_000 정점
m <= 200_000 간선
*/

public class Main {
    public static int n, m;
    public static List<List<Integer>> graph = new ArrayList<>();
    public static List<List<Integer>> reverseGraph = new ArrayList<>();
    public static boolean[] toS;
    public static boolean[] toT;
    public static boolean[] fromS;
    public static boolean[] fromT;
    
    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 s = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            graph.get(s).add(t);
            reverseGraph.get(t).add(s);
        }

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

        toS = new boolean[n+1];
        toT = new boolean[n+1];
        fromS = new boolean[n+1];
        fromT = new boolean[n+1];

        // 초기화 s-t 가 연결되었다는 가정
        fromS[t] = true;
        fromT[s] = true;
        
        dfs(s, fromS, graph); // s에서 도달 가능한 정점
        dfs(t, fromT, graph); // t에서 도달 가능한 정점
        dfs(s, toS, reverseGraph); // s로 들어올 수 있는 정점
        dfs(t, toT, reverseGraph); // t로 들어올 수 있는 정점

        int count = 0;
        for (int i=1; i<=n; i++) {
            if (toS[i] && toT[i] && fromS[i] && fromT[i]) {
                count++;
            }
        }
        System.out.print(count - 2); // 출발, 도착 지점 제외
    }

    public static void dfs(int v, boolean[] visited, List<List<Integer>> graph) {
        if (visited[v]) {
            return;
        }

        visited[v] = true;
        
        for (int next : graph.get(v)) {
            dfs(next, visited, graph);
        }
    }
}

전에 한번 비슷한 문제를 풀어본 것 같아서 호기롭게 도전했지만 바로 실패했다.
이번에 정확하게 이해하고 가는 것 같아서 다음 번에 비슷한 유형의 문제는 틀리지 않겠다!