[SWEA/D3/DFS/자바] 최장 경로

💡 문제

 

N개의 정점과 M개의 간선으로 구성된 가중치가 없는 무방향 그래프에서의 최장 경로의 길이를 계산하자.
정점의 번호는 1번부터 N번까지 순서대로 부여되어 있다.
경로에는 같은 정점의 번호가 2번 이상 등장할 수 없으며, 경로 상의 인접한 점들 사이에는

반드시 두 정점을 연결하는 간선이 존재해야 한다.
경로의 길이는 경로 상에 등장하는 정점의 개수를 나타낸다.

 

⌨ 입력 

 

첫째 줄 : 테스트 케이스 수 (T)

둘째 줄 : 각 테스트 케이스의 N, M ( 1 <= N <= 10 ) , ( 0 <= M <= 20 )

M개의 줄 : 그래프 간선 정보 x y  ( 1 <=  x , y <=  N )

 

💻 출력 / 제한

 

그래프에서의 최장 경로의 길이를 출력한다. / 1개 테스트 케이스 당 0.2초

 

---

 

풀이 방법 

 

최장 경로의 뜻을 몰랐다. 코딩 테스트라 생각하고 입력을 보고 유추 해본 결과,   

각 노드에 dfs 를 해서 가장 길게 연결된게 아닐까 했다.

( 정점 : 노드 / 간선 : 노드를 잇는 선  / 무방향 : 양쪽에서 모두 접근 가능 )

 

 

결과 : 테스트 케이스 10개 중 5개 맞습니다....???

 

최장 경로의 뜻을 알아 보았다.

그래프 이론에서, [경로]는 같은 꼭짓점을 거듭 거치지 않는 변들의 열이다. - 위키백과

 

내가 푼 것과 차이를 알아보자.

 

 

 

위 그래프에서 1번 노드에 dfs를 하면 1 - 2 - 3 - 4 - 5  모두 연결 된다.

하지만 문제에서 원하는 것은 1번 노드를 다시 거치지 않고 가장 길게 연결 하는 것 이다.

 

1  >  2  >  3  /  1  >  4  >  5  로 되는 것이다. 그레서 1번 노드의 답은 3이다.

코드를 수정 한후, dfs(index, count) 로 해서 다시 dfs를 돌렸다.

( index : 시작 노드  /   count  :  연결 된 노드의 수 )

 

결과 : 테스트 케이스 10개중 7개 맞았습니다. .....?

 

반례를 통해 문제점을 알아보자.

 

 

 

위와 같은 그래프가 있을때 3번노드를 방문 체크 후, DFS(4)  DFS(7) 를 호출 한다.

호출 순서상 DFS(4) 가 먼저 호출 된다. 그러면 4, 5, 6 노드를 다 방문 체크한다.

그리고 DFS(7) 호출 되면 7번 노드는 4, 5, 6 노드가 다 방문 체크 되어 가지 못하는 것 이다. 

 

그레서 정답은 1 > 2 > 3  > 7 > 4 > 5 > 6  답은 7이다.

하지만 방문 체크를 해버리면 1 > 2  > 3  >  4  > 5  > 6  답 : 6  틀리게 된다.

DFS() 를 호출 한후에 더 이상 갈 노드가 없으면 방문 체크를 해제 하여 테스트를 통과 했다. 

 

전체 코드

 

import java.util.ArrayList;
import java.util.Scanner;

public class CriticalPath {

    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> list;
    static int max = 0;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int testCase = sc.nextInt();
        StringBuilder sb = new StringBuilder();

        for(int t = 1; t <= testCase; t++) {
            int nodeNum = sc.nextInt();
            int lineNum = sc.nextInt();

            list = new ArrayList<>();
            visited = new boolean[nodeNum + 1];

            for (int i = 0; i <= nodeNum; i++) {
                list.add(new ArrayList<>());
            }

            for (int i = 0; i < lineNum; i++) {
                int line1 = sc.nextInt();
                int line2 = sc.nextInt();
                list.get(line1).add(line2);
                list.get(line2).add(line1);
            }

            for(int i = 1; i <= nodeNum; i++){
                dfs(i,1);
            }

            String st = "#" + t + " " + max;
            sb.append(st).append("\n");
            max = 0;
        }
        System.out.print(sb);
    }

    static void dfs(int index, int count){

        if(max < count) max = count;

        int newCount = count + 1;
        ArrayList<Integer> connectList = list.get(index);

        for (int node : connectList) {
            if(!visited[node]) {
                visited[index] = true;
                dfs(node, newCount);
                visited[index] = false;
            }
        }
    }
}