[SWExpert] 2814. 최장경로

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE

SW Expert Academy

풀기 전 생각

• DFS를 사용해서 풀어야겠다. 무한루프에 빠지지 않기 위해 방문한 노드들을 확인한다.

• 이 때, 다음에 돌 때를 위해 방문한 노드들을 다시 false로 만들어준다. 

  • 예를 들어 아래의 경우 노드 2를 방문하고 난 후 노드 3으로 갈 때 방문표시를 false로 하지 않으면 1->2->3->4으로 끝나버린다.

  • 하지만 1->2->5->6->3->4 가 최장경로이다.

• 주의!! 꼭 1부터 시작한다는 보장이 없다!!

---

코드

package swexpert.D3;

import java.util.Scanner;

public class 최장경로_SW2814 {
    static boolean map[][], visited[];
    static int n, result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            n = sc.nextInt();       //n : n개의 정점
            int m = sc.nextInt();       //m : m개의 간선
            map = new boolean[n + 1][n + 1];
            result = 0;
            visited = new boolean[n + 1];
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                map[a][b] = true;
                map[b][a] = true;
            }

            for (int i = 1; i <= n; i++) {
                visited[i] = true;
                dfs(i, 1);
                visited[i] = false;
            }
            System.out.println("#" + t + " " + result);
        }
    }

    private static void dfs(int idx, int cnt) {
        if (result < cnt)
            result = cnt;

        for (int i = 1; i <= n; i++) {
            if (map[idx][i] && !visited[i]) {
                visited[i] = true;
                dfs(i, cnt + 1);
                visited[i] = false;

            }
        }

    }
}