[SWEA 2814번] 최장경로

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=2

SW Expert Academy

 

 

 

import java.io.*;
import java.util.*;
 
public class Solution {
 
 
    static int N;
 
    static int M;
 
    static int[][] graph;
 
    static int cnt;
    static int result;
 
    static boolean[] visit;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
 
        for (int test = 1; test <= T; test++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
            graph = new int[N + 1][N + 1];
            visit = new boolean[N + 1];
            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int fNode = Integer.parseInt(st.nextToken());
                int bNode = Integer.parseInt(st.nextToken());
                graph[fNode][bNode] = bNode;
                graph[bNode][fNode] = fNode;
            }
            result = 1;
            cnt = 1;
 
            for (int i = 1; i < N + 1; i++) {
 
                dfs(i);
            }
 
            System.out.println("#" + test + " " + result);
        }
    }
 
    private static void dfs(int currentNode) {
        if (cnt == N) {
            return;
        }
 
        for (int i = 1; i < N + 1; i++) {
            if (currentNode == i) {
                continue;
            }
            if (graph[currentNode][i] != 0 && !visit[i]) {
                visit[currentNode] = true;
                cnt++;
                result = Math.max(result, cnt);
 
                dfs(i);
                cnt--;
                visit[currentNode] = false;
            }
        }
 
    }
}

 

어제 다이스트라 복습 문제 풀어서 오늘 이 문제 풀고 다이스트라 처럼 접근하다가 실수 엄청했다...

가장 기본적인 DFS 문제인데 뭐한거지??? ㅋㅋ

 

핵심은 visit boolean 배열과 재귀함수를 이용해서 풀면 된다.