[SWEA] 2814. 최장 경로

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

---

접근 방법

이 문제를 풀면서 DFS와 백트래킹에 대해 이해했다.

둘 다 완전 탐색이지만 백트래킹은 가지치기를 한다는 점에서 차이가 있다. (N-Queen, 배낭 문제, 순열/조합)

 

Array 안에 ArrayList를 저장하는 구조를 사용했다.

재귀 함수가 check를 참고하여 일을 마치고 오면 check를 원 상태로 되돌리는 과정이 2번 중복된다.

 

소스 코드

import java.util.*;
 
class Solution
{
    static int count = 0;
    static boolean[] ck;
    static ArrayList<Integer>[] num;
     
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T=sc.nextInt();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int M = sc.nextInt();
            count = 0;
            ck = new boolean[N];
            Arrays.fill(ck, false);
            num = new ArrayList[N];
            for(int i=0; i<N; i++)
                num[i] = new ArrayList<>();
             
            for(int i=0; i<M; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                num[x-1].add(y-1);
                num[y-1].add(x-1);
            }
            for(int i=0; i<N; i++) {
                ck[i] = true;
                dfs(i, 1);
                ck[i] = false;
            }
            System.out.println("#" + test_case + " " + count);
        }
    }
    static void dfs(int i, int cnt) {
        count = Math.max(count, cnt);
        for(int n : num[i]) {
            if(!ck[n]) {
                ck[n] = true;
                dfs(n, cnt+1);
                ck[n] = false;
            }
        }
    }
}