출퇴근길

문제 정의

• 출발 노드와 도착 노드가 정해져있다.
• 단방향 그래프에서 출발 노드 -> 도착노드를 가면서 그 사이에 방문하게 되는 노드들이 있을 것이고, 도착 노드 -> 출발 노드까지 가면서 방문하는 노드들이 있을 것이다.
• 이때, 출발지 -> 도착지로 가면서 만나면서도, 도착지 -> 출발지로 가면서도 만나게 되는 노드들을 구해라

문제 해결 접근

• 특정 정점이 출발지 -> 도착지 가는 중에서 있으려면, 4가지 조건이 필요하다
  
  1. 출발지에서 해당 정점까지 갈 수 있어야함
  2. 해당 정점에서 도착지까지 갈 수 있어야함
  3. 도착지에서 해당 정점까지 갈 수 있어야함
  4. 해당 정점에서 출발지까지 갈 수 있어야함
• 그렇게 하기 위해서는, 역방향 그래프를 두어서, 도착지 -> 해당 정점까지 갈 수 있는지를 판단해야한다.

코드

import java.util.*;
import java.io.*;
public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n,m,s,t;
    static boolean[] visit_normal_start, visit_normal_end, visit_reverse_start, visit_reverse_end;
    static ArrayList<ArrayList<Integer>> graph_normal = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> graph_reverse = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for(int i = 0;i<=n;i++){
            graph_normal.add(new ArrayList<>());
            graph_reverse.add(new ArrayList<>());
        }
        visit_normal_start = new boolean[n+1];
        visit_normal_end = new boolean[n+1];
        visit_reverse_start = new boolean[n+1];
        visit_reverse_end = new boolean[n+1];
        for(int i = 0;i<m;i++){
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            graph_normal.get(start).add(end);
            graph_reverse.get(end).add(start);
        }
        // Please write your code here.
        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        bfs(s,t,graph_normal,visit_normal_start);// 시작 -> 끝으로 갈 때, 거치는 모든 정점 탐색
        bfs(t,s,graph_normal,visit_normal_end); // 끝 -> 시작으로 갈 때, 거치는 모든 정점 탐색
        bfs(s,-1,graph_reverse,visit_reverse_start); // 역방향 그래프에서, 시작 -> 끝으로 갈 때  거치는 모든 정점 탐색
        bfs(t,-1,graph_reverse,visit_reverse_end); // 역방향 그래프에서, 끝 -> 시작으로 갈 때, 거치는 모든 정점 탐
        int answer = 0;
        for(int i = 1;i<=n;i++){
            if(i==s||i==t)
                continue;
            if(visit_normal_start[i]&&visit_normal_end[i]&&visit_reverse_start[i]&&visit_reverse_end[i])
                answer++;
        }
        System.out.println(answer);
    }
    static void bfs(int start, int end,ArrayList<ArrayList<Integer>> graph, boolean[] visit){
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        visit[start]= true;
        while(!queue.isEmpty()){
            int cur = queue.poll();
            if(cur==end)
                continue;
            for(int i :graph.get(cur)){
                if(visit[i])
                    continue;
                visit[i] = true;
                queue.add(i);
            }
        }
    }
}
// 출발지에서 특정 정점으로 갈 수 있다 : normal_visit_start[i] = true
// 도착지에서 특정 정점으로 갈 수 있다 : normal_visit_end[i] = true
// 특정 정점에서, 출발지로 갈 수 있다 : reverse_visit_start[i] = true
// 특정 정점에서, 도착지로 갈 수 있다 : reverse_visit_end[i] = true

느낀점

• 역방향 그래프를 두어서, 특정 정점에서 목적지까지 갈 수 있는 걸 확인할 수 있다는 것을 느꼈다.