출퇴근길

작성일: 2024-10-31

문제 링크 : https://softeer.ai/practice/6248

접근 방식

인접 리스트에 출퇴근 경로를 저장한다.

출발지부터 도착지까지 이동하면서, 방문한 정점을 기록한다.

출퇴근길간의 정점을 비교해서, 중복되는 정정의 개수를 리턴한다.

잘못된 접근

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

public class Main {

    static LinkedList<Integer>[] list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int result = 0;
        int n = sc.nextInt(); // 정점 수
        int m = sc.nextInt(); // 간선 수
        list = new LinkedList[n+1];
        for(int i=1; i<=n; i++){
            list[i] = new LinkedList();
        }
        for(int i=0; i<m; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            list[start].add(end);
        }
        int S = sc.nextInt(); // 집의 정점 번호
        int T = sc.nextInt(); // 회사의 정점 번호
        boolean visited1[] = new boolean[n+1];
        boolean visited2[] = new boolean[n+1];
        dfs(S, T, visited1);
        dfs(T, S, visited2);
        for(int i=1; i<=n; i++){
            if(i!=S && i!=T && visited1[i] && visited2[i]) result++;
        }

        System.out.println(result);
    }

    private static void dfs(int start, int end, boolean[] visited) {
        if(visited[start]) return;
        visited[start] = true;
        if(start==end) return;
        for(int i:list[start]){
            dfs(i, end, visited);
        }
    }
}

일부 상황에서, 오답이 발생했다.
디테일한 점이 부족했다.

나는 집에서 회사로 가는 모든 방식을 알고자했다.

하지만, 코드는 모든 방식이 아니라 일부 상황만을 고려한 코드였다.

현재 내 코드는, start부터 end까지 가면서 방문처리를 한다.

여기서 두 가지 기저조건을 통해 재귀를 탈출하고 있다.
하나는, 이미 방문했던 곳이라면 가지 않기
두번째는, 도착지라면 돌아가기

여기서 중요한 점은 갈 수 있는 경로만 찾을 수 있다는 것이다.

현재 문제는 도착지를 제외한 중복 방문을 허용하고 있다. 따라서 원래 코드에서는 이미 방문한 노드의 경우 방문처리를 통해 더 이상 방문하지 않기 때문에 어떻게든 도착지에 도착하는 경우는 포함하고 있지 않다.

따라서, 특정 노드에서 출발지 혹은 도착지에 갈 수 있는지 여부가 중요한 것이다.
그래서 역방향 그래프를 떠 올릴 수 있는지가 이 문제에서 중요한 쟁점이다.

결과

소스 코드

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

public class Main {

    static LinkedList<Integer>[] list;
    static LinkedList<Integer>[] rlist;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int result = 0;
        int n = sc.nextInt(); // 정점 수
        int m = sc.nextInt(); // 간선 수
        list = new LinkedList[n+1];
        rlist = new LinkedList[n+1];
        for(int i=1; i<=n; i++){
            list[i] = new LinkedList();
            rlist[i] = new LinkedList();
        }
        for(int i=0; i<m; i++){
            int start = sc.nextInt();
            int end = sc.nextInt();
            list[start].add(end);
            rlist[end].add(start);
        }
        int S = sc.nextInt(); // 집의 정점 번호
        int T = sc.nextInt(); // 회사의 정점 번호
        boolean visited1[] = new boolean[n+1];
        boolean visited2[] = new boolean[n+1];
        boolean visited3[] = new boolean[n+1];
        boolean visited4[] = new boolean[n+1];
        dfs(S, T, visited1);
        dfs(T, S, visited2);
        rdfs(S, visited3);
        rdfs(T, visited4);
        for(int i=1; i<=n; i++){
            if(i!=S && i!=T && visited1[i] && visited2[i] && visited3[i] && visited4[i]) result++;
        }

        System.out.println(result);
    }

    private static void dfs(int start, int end, boolean[] visited) {
        if(visited[start]) return;
        visited[start] = true;
        if(start==end) return;
        for(int i:list[start]){
            dfs(i, end, visited);
        }
    }
    private static void rdfs(int start, boolean[] visited) {
        if(visited[start]) return;
        visited[start] = true;
        for(int i:rlist[start]){
            rdfs(i, visited);
        }
    }
}

알게 된 점

그래프간의 정점과 간선을 인접 리스트로 표현할 때

특정 좌표까지의 도달 가능성을 생각해야하는 경우에는

역방향 그래프를 통해 모든 경우의 수를 생각할 수 있음을 알게되었다.