[소프티어] 출퇴근길 자바 풀이 DFS 레벨3 (HSAT 6회 정기 코딩 인증평가 기출)

[소프티어] 출퇴근길 자바 풀이 레벨3 (HSAT 6회 정기 코딩 인증평가 기출)

https://softeer.ai/practice/6248

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

 

 

 

 

 

이 녀석은 새벽까지 날 못자게 한 녀석이다.

설명도 찰떡같이 해둔분이 안계신거 같아서, 내가 각잡고 예쁘게 적어보고 싶었다.

 

문제 스펙

 

 

 

 

 

 

 

 

핵심 요약

- 출근길과 퇴근길에 모두 포함되는 정점 구해야 함.

- DFS와 역방향 간선 그래프를 이용해야 함.

- 정방향 a출발 DFS 결과들 && 역방향 b출발 DFS 결과들 = "a-> b" 도달 가능한 경로를 의미함.

 

 

- 출근길 경로 a->b를 구하기 위해

         정방향 a출발 DFS   (단, b도착시 움직이지 못하게 visit true 우선처리 필요)

                 예시는 1->7일때, 1에서의 도달가능정점들은 23   54   8   7(멈춤) 이다.

         역방향 b출발 DFS

                 예시는 7->1일때, 7에서의 도달가능정점들은 851(안멈춤)324  6 이다.

         총 2개 세트 구현.

 

- 퇴근길 경로 b->a를 구하기 위해

         정방향 b출발 DFS  (단, a도착시 움직이지 못하게 visit true 우선처리 필요)

                  예시는 7->1일때, 7에서의 도달가능정점들은 762  31(멈춤) 이다.

         역방향 a출발 DFS

                  예시는 1->7일때, 1에서의 도달가능정점들은 13245  7(안멈춤)8  6 이다

         총 2개 세트 구현.

 

- 출근길 DFS 2개 && 퇴근길 DFS 2개 = {2, 3} = 출력 2

 

- 테스트케이스 (입력 예시 2에서 마지막 st값만 변경했습니다)

8 14
1 2
1 5
1 7
2 3
3 1
4 1
4 2
5 4
5 8
6 2
6 3
7 1
7 6
8 7
7 1 (혹은 1 7)

- 출력결과

 

 

 

 

 

 

 

 

 

 

 

주석 참고해주세요

 

 

 

 

전체 코드

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

public class Main {

    public static int n, m, s, t;
    public static ArrayList<ArrayList<Integer>> arrList = new ArrayList<ArrayList<Integer>>(); // 정순
    public static ArrayList<ArrayList<Integer>> reverseList = new ArrayList<ArrayList<Integer>>(); // 역순
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        // int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 정점 생성
        for(int i=0; i<n; i++){
            arrList.add(new ArrayList<Integer>());
            reverseList.add(new ArrayList<Integer>());
        }

        // 정점 별 간선 세팅
        for(int i=0; i<m; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken())-1;
            int y = Integer.parseInt(st.nextToken())-1;
            arrList.get(x).add(y);
            reverseList.get(y).add(x);
        }

        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.write(String.valueOf(dap));
        bw.flush();
        bw.close();
    }

    public static int sol(){ // start=1, end3
        boolean[] arrStartS = new boolean[n];
        //arrStartS[s]=true; // 출근 경로에 S 여러번 등장 가능
        arrStartS[t]=true; // 끝나는 정점을 미리 visited처리
        
        boolean[] arrStartT = new boolean[n];
        arrStartT[s]=true; // 끝나는 정점을 미리 visited처리
        //arrStartT[t]=true; // 퇴근 경로에 T 여러번 등장 가능
        
        boolean[] reverseStartS = new boolean[n];
        //reverseStartS[s]=true;
        // reverseStartS[t]=true; // "출근길에 S는 여러번 등장해도 되고, 퇴근길에 T는 여러번 등장해도 된다." 라는 조건 때문에 역방향 DFS 두가지에서는 각각 끝나는 정점을 미리 visited 처리 하지 않아야 함.
        
        boolean[] reverseStartT = new boolean[n];
        // reverseStartT[s]=true; // "출근길에 S는 여러번 등장해도 되고, 퇴근길에 T는 여러번 등장해도 된다." 라는 조건 때문에 역방향 DFS 두가지에서는 각각 끝나는 정점을 미리 visited 처리 하지 않아야 함.
        //reverseStartT[t]=true;
        
        dfs(arrList, arrStartS, s); // 정방향 간선 통해 S->T 이동, T도착시 못움직임 (끝나는 정점을 미리 visited처리)
        dfs(arrList, arrStartT, t); // 정방향 간선 통해 T->S 이동, S도착시 못움직임 (끝나는 정점을 미리 visited처리)
        
        dfs(reverseList, reverseStartS, s); // 역방향 간선 통해 S->T 이동 (끝나는 정점을 미리 visited처리하지 않음)
        dfs(reverseList, reverseStartT, t); // 역방향 간선 통해 T->S 이동 (끝나는 정점을 미리 visited처리하지 않음)

        int dap = 0;
        for(int i=0; i<n; i++){
            if(arrStartS[i] && arrStartT[i] && reverseStartS[i] && reverseStartT[i] && i!=s && i!=t){
                System.out.print(i+1 + ",");
                dap++;
            }
        }
        System.out.println();
        return dap;
    }

    public static void dfs(ArrayList<ArrayList<Integer>> g, boolean[] visit, int cur){
        if(visit[cur] == true) return;

        visit[cur] = true;
        for(int next : g.get(cur)){ // 한 정점에 인접된 간선을 보고
            dfs(g, visit, next);
        }
    }
}