[Softeer/Java] 6248. 출퇴근길

[Softeer/Java] 6248. 출퇴근길

Softeer - 현대자동차그룹 SW인재확보플랫폼

---

문제 해석

동환이는 자동차로 출퇴근을 하면서 가끔 길을 바꾸어 다니며 새로운 동네를 발견하는 것을 즐긴다. 이 문제에서는 동환이의 출퇴근길을 단방향 그래프로 나타내어, S에서 T로의 출근길과 T에서 S로의 퇴근길에 모두 방문할 수 있는 동네(정점)의 개수를 찾는다. 각 정점은 동네를, 간선은 도로를 의미하며, 각 도로는 일방통행이다. 문제는 출퇴근길에서 공통적으로 방문 가능한 정점을 찾는 것에 초점을 맞추어 있다.

풀이 과정

1. 그래프 구성: n개의 정점과 m개의 일방통행 간선 정보를 입력받아 그래프를 구성한다. 또한, 각 정점에서 출발하는 간선 리스트와 각 정점으로 도착하는 간선 리스트를 각각 관리한다.
2. DFS 수행: 출근길에 해당하는 S에서 T로의 경로와 퇴근길에 해당하는 T에서 S로의 경로를 각각 탐색하기 위해 깊이 우선 탐색(DFS)를 이용한다.
3. 정점 방문 여부 체크: DFS를 통해 각 경로를 탐색하며 방문한 정점들을 마킹한다. 이때, S에서 T로 가는 경로와 T에서 S로 돌아오는 경로에서 모두 방문한 정점만을 최종적으로 세어 문제의 조건에 맞는 정점의 개수를 계산한다.

코드

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

public class Main {
    private static int N, M, S, T;
    private static ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
    private static ArrayList<ArrayList<Integer>> reverseList = new ArrayList<>();
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        for(int i=0; i<N; i++) {
            arrayList.add(new ArrayList<>());
            reverseList.add(new ArrayList<>());
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken()) - 1;
            int v = Integer.parseInt(st.nextToken()) - 1;
            arrayList.get(u).add(v);
            reverseList.get(v).add(u);
        }
        
        st = new StringTokenizer(br.readLine());
        S = Integer.parseInt(st.nextToken()) - 1;
        T = Integer.parseInt(st.nextToken()) - 1;
        
        sb.append(sol());
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        // 출근길
        boolean[] v1 = new boolean[N];
        v1[T] = true;
        dfs(S, arrayList, v1);

        boolean[] v2 = new boolean[N];
        dfs(T, reverseList, v2);

        // 퇴근길
        boolean[] v3 = new boolean[N];
        v3[S] = true;
        dfs(T, arrayList, v3);

        boolean[] v4 = new boolean[N];
        dfs(S, reverseList, v4);

        int ans = 0;
        for (int i=0; i<N; i++) {
            if (v1[i] && v2[i] && v3[i] && v4[i]) ans++;
        }

        return ans-2;
    }

    private static void dfs(int current, ArrayList<ArrayList<Integer>> graph, boolean[] v) {
        if(v[current]) return;
        
        v[current] = true;
        for (int next : graph.get(current)) {           
            dfs(next, graph, v);
        }   
    }
}

시간 복잡도 분석

이 문제의 풀이에서 시간 복잡도는 주로 DFS에 의해 결정된다. DFS의 경우 각 정점을 한 번씩 방문하며, 모든 간선을 검토한다. 따라서 시간 복잡도는 O(N + M)이다. 주어진 입력 제약에서는 최대 100,000개의 정점과 200,000개의 간선을 다루므로, 이 알고리즘은 충분히 효율적이다.

느낀점

이 문제를 통해 단방향 그래프에서 두 정점 간의 경로 문제를 해결하는 방법을 더욱 잘 이해할 수 있었다. 또한, DFS를 활용하여 복잡한 그래프 구조에서 특정 조건을 만족하는 정점을 찾는 방법에 대해 심도 있게 고민할 수 있는 좋은 기회였다.