소프티어 [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길 [Java]

문제

https://softeer.ai/practice/6248

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

 

코드

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

public class Main {
    static int n, m, home, company;
    static List<List<Integer>> graph, reverseGraph;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        graph = new ArrayList<>();
        reverseGraph = new ArrayList<>();
        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<>());
        }
        HashSet<Integer> goCompany = new HashSet<>();
        HashSet<Integer> goCompanyReverse = new HashSet<>();
        HashSet<Integer> goHome = new HashSet<>();
        HashSet<Integer> goHomeReverse = new HashSet<>();
        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph.get(a).add(b);
            reverseGraph.get(b).add(a);
        }
        st = new StringTokenizer(br.readLine());
        home = Integer.parseInt(st.nextToken());
        company = Integer.parseInt(st.nextToken());

        dfs(home, company, graph, goCompany, new boolean[n + 1]);
        dfs(company, -1, reverseGraph, goCompanyReverse, new boolean[n + 1]);
        goCompany.retainAll(goCompanyReverse);

        dfs(company, home, graph, goHome, new boolean[n + 1]);
        dfs(home, -1, reverseGraph, goHomeReverse, new boolean[n + 1]);
        goHome.retainAll(goHomeReverse);

        goCompany.retainAll(goHome);

        int answer = goCompany.size();
        if(goCompany.contains(home)) answer--;
        if(goCompany.contains(company)) answer--;
        System.out.println(answer);
    }

    static void dfs(int start, int end, List<List<Integer>> g, HashSet<Integer> set, boolean[] visited) {
        if(end != -1 && start == end) return;

        for(int next : g.get(start)) {
            if(!visited[next]) {
                visited[start] = true;
                set.add(next);
                dfs(next, end, g, set, visited);
            }
        }
    }
}

 

접근 방법

주어진 정점에 따라 단방향 그래프를 만들고 출발지에서 도착지로 갈 수 있는 모든 경우를 탐색한다.

집 -> 회사 / 회사 -> 집 두가지 경우로 모두 탐색을 하고 각각 방문한 점을 비교했다.

굉장히 간단한 탐색 문제라고 생각했다.

 

시행 착오

일단 아무 생각 없이 BFS탐색을 했다. 검색해보니 DFS를 사용해야한다고 하는데 이게 정말 이해가 안돼서 어느 문제에 어떻게 사용해야하는지 찾아보았다.

 

DFS를 사용해야할 때

• 경로의 특징을 저장해야하는 문제
• 검색 대상 그래프가 큰 경우

 

BFS를 사용해야할 때

• 미로 찾기 등 최단 거리를 구해야할 때
• DFS는 처음으로 발견된 해답이 최단거리라는 보장이 없다.

 

이 문제의 경우에는 지나간 지점들을 기억하고 있어야 하기 때문에 DFS로 풀어야 한다.

 

이 문제에서 찾아야 하는 정점은 집에서도 도달가능해야하고, 회사에서도 도달이 가능해야한다는 두가지 특징을 갖는다. 그렇다면 임의의 정점 V가 출발지 혹은 도착지에 도달가능한지 모든 정점을 시작으로 DFS탐색을 하는건 시간상의 문제로 할 수 없다. 이걸 해결하는 방법이 역방향 그래프를 이용하는거라고 한다. 여기서 생겼던 의문은 그렇다면 양방향 그래프랑 단방향이면서 역방향까지 확인하는 것의 차이가 이해가 가는듯하면서 정확히 이해가 가지 않았다.

 

단방향 그래프에서 역방향까지 탐색해야하는 이유는 도착지에서 출발지로의 경로를 역탐색하면서 상호접근가능한 노드들을 파악해야하기 때문이라고 한다. 단방향 그래프 문제를 해결할 대 모든 간선이 양방향으로 바뀌면 출발지와 도착지를 바꾸어도 같은 결과가 나오지만 단방향 & 역방향의 방문정점 교집합을 찾으면 상호접근이 가능한 노드이다.

 

처음 탐색할 때는 end를 도착지로 설정한다. 출발지에서 도착지의 경로를 찾고 도착지에 도달하면 더 이상 탐색을 하지 않는다.

하지만 역방향으로 탐색할 때는 end를 -1로 넘겨준다. 이는 탐색을 특정 도착지가 없이 전체적으로 하기 위해서이다.

 

아무튼 오늘의 교훈은

단방향 그래프 탐색 문제인데 정점을 상호접근가능한지 확인하기 위해선 역방향 그래프가 필요하다는 사실을 기억하면 좋을거 같다.