경로 탐색(인접행렬)

문제

풀이

public class Main {

    static int targetNodeNum;
    static Map<Integer, List<Integer>> map = new HashMap<>();

    // 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        targetNodeNum = sc.nextInt();
        int edgeNum = sc.nextInt();

        for(int i = 0; i<edgeNum; i++){
            int startNode = sc.nextInt();
            int endNode = sc.nextInt();
            List<Integer> endNodeList = map.getOrDefault(startNode, new ArrayList<>());
            endNodeList.add(endNode);
            map.put(startNode, endNodeList);
        }
        dfs(1, new ArrayList<>());
    }

    private static void dfs(int current, List<Integer> route) {
        route.add(current);
        if(current == targetNodeNum){
            route.forEach(node -> System.out.print(node + " "));
            System.out.println();
        }else{
            List<Integer> myTargetNodes = map.get(current);
            myTargetNodes.forEach(myTarget -> {
                if(!route.contains(myTarget)){
                    List<Integer> newRoute = new ArrayList<>(route);
                    dfs(myTarget, newRoute);
                }
            });
        }

    }
}

풀이

1. 그래프를 이차원 배열로 표현하기보단 자신이 가지고 있는 target node 정보만 가지고 있는게 나을 것 같아서 map 사용
2. 지나왔던 노드는 다시 지나갈 수 없기 때문에 이를 기록할 boolean배열을 두었다가, 말단 노드에 도달하는 경우 boolean배열을 이전 분기점까지 다시 초기화해줘야 하는데 방법이 생각나지 않아 boolean배열을 사용하지 않고 넘겨받은 route에 타겟 노드가 포함되어있는지로 해당 노드를 이미 지나왔는지 판단
   2.1 (추가) boolean배열 사용 시 분기점 이후의 지나온 지점을 초기화하는 방법은 그냥 dfs호출 이후 방금 지나온 target의 visited를 false로 다시 바꾸면 된다
3. route는 분기가 다른 루트마다 다른 객체여야 하므로 새로운 노드로 분기하는 경우 이전의 route정보를 복사하여 새로운 route객체를 넘겨 다음 노드에 넘겨주었다.