[2023-05-23] 소프티어 출퇴근길

문제 링크 : https://softeer.ai/practice/info.do?idx=1&eid=1529&sw_prbl_sbms_sn=203929 

Softeer

 

언어별 시간/메모리

언어시간메모리

C	2초	1024MB
C++	2초	1024MB
Java	4초	1024MB
Python	4초	1024MB
Javascript	4초	1024MB

문제

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

 

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

 

동환이의 출퇴근길은 단방향 그래프로 나타낼 수 있다. 즉, 각 동네를 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로 가는 경로가 하나 이상 존재함이 보장된다.

* 간선의 양 끝 점은 서로 다르다.

* 같은 정점쌍을 같은 방향으로 잇는 간선은 두 개 이상 주어지지 않는다.

입력형식

첫째 줄에 정점과 간선의 개수를 나타내는 두 정수 n과 m이 주어진다. 이어 m개의 줄에는 간선의 정보를 나타내는 두 정점의 번호 xi와 yi가 주어진다. 이는 xi에서 yi로 가는 단방향 간선이 존재함을 의미한다. 마지막 줄에는 동환이의 집과 회사의 위치에 해당하는 정점 번호 S와 T가 주어진다.

출력형식

첫째 줄에 출근길과 퇴근길 모두에서 방문 가능한 정점의 개수를 출력한다.

 

---

해결 과정

가장 먼저 든 해결 방법은 S에서 T로 가는 길 DFS를 하고 T에서 S로 가는 길을 DFS로 하여 교집합을 구하면 다 계산이 되지 않을까하는 생각이었다. DFS의 한번 시간 복잡도는

O(V + E)로 2*O(V + E)의 시간 복잡도 안에 계산할 수 있을 것이라고 생각했다. 하지만 결과는 Fail..

이 후 반례를 생각해보았다. 

만약 다음과 같은 그래프가 있다면  2번 노드는 고려되지 않는다. 그렇다면 이를 어떻게 해결할 수 있을까?
해결 방법은  S에서 T로 가는 길, T에서 S로 가는 길로 DFS를 하는 게 아니라, S에서 갈 수 있는 길, T에서 갈 수 있는 길, S로 들어오는 길, T로 들어갈 수 있는 길 4가지 DFS를 하여 4개의 DFS의 교집합을 구하는 방법이었다. 이 때 주의해야할 점은 위의 3번 노드 같은 케이스가 고려되지 않도록 하는 점이다. 만약 T와 3번이 왕복이 가능하다고 해도 3번은 포함되면 안된다. T에 도착하면 움직이면 안되기 때문이다. 이를 위해 S와 T를 먼저 방문 배열에 추가해주고 DFS를 시작해주었다.
 
사실 이 부분은 내가 직접 떠올리지 못해 친구의 도움을 많이 받았다.. 해결법을 들어도 이해하는데까지도 시간이 많이 걸린 문제였다. 내가 생각하던 기존의 DFS의 틀을 깨야 풀 수 있는 문제인 듯 싶다.

---

코드

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


public class Main
{
    static int n;
    static int m;
    static boolean[] fromS;
    static boolean[] fromT;
    static boolean[] toS;
    static boolean[] toT;
    static int ans;
    static int S;
    static int T;
    static ArrayList<Integer>[] graph;
    static ArrayList<Integer>[] graphR;
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());

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

        graph = new ArrayList[n+1];
        graphR = new ArrayList[n+1];
        for(int i = 0 ; i <=n ;i++){
            graph[i] = new ArrayList<>();
            graphR[i] = new ArrayList<>();
        }

        for(int i = 0 ; i < m; i++){
            stk = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stk.nextToken());
            int b = Integer.parseInt(stk.nextToken());
            graph[a].add(b); // direct graph (a2b)
            graphR[b].add(a); // direct graph (b2a)
        }
        stk = new StringTokenizer(br.readLine());
        S = Integer.parseInt(stk.nextToken());
        T = Integer.parseInt(stk.nextToken());


        fromS[T] = true;
        fromT[S] = true;

        dfs(S, fromS, graph);
        dfs(T, fromT, graph);
        dfs(S, toS, graphR);
        dfs(T, toT, graphR);

        for(int i = 1; i<=n; i++){
            if(fromS[i]&&fromT[i]&&toS[i]&&toT[i]){
                ans++;
            }
        }
        System.out.println(ans-2);
    }
    public static void dfs(int v, boolean [] visited, ArrayList<Integer>[] graph){
        if(visited[v]){
            return;
        }
        visited[v] = true;
        for(int ele : graph[v]){
            dfs(ele, visited, graph);
        }
    }

}