[삼성 SW Expert Academy] 2814. 최장 경로 [JAVA]

 

| Problem

※ SW Expert Academy는 문제의 무단 복제를 금지하고 있기 때문에, 기재하지 못한 점 양해 부탁드립니다.

| Link

※ 하단의 Link를 클릭해도, 로그인 후 열람이 가능합니다.

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB

SW Expert Academy

---

| 풀이

1. 최대 N 개의 정점이다. ArrayList로 부터 연결된 각 노드에서 최대 N개의 경로로 들어가도록 하자. ( DFS )

2. ex) 시작 점을 0부터 시작해서 연결된 노드로 쭉 들어가며 깊이 우선 탐색하기.

---

| 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class 최장경로_2814 {
	
	static int Tc;   // Tc
	static int N, M; // N - 정점의 개수, M - 간선의 개수 
	static ArrayList<Integer>[] start;   
	static int answer; 
	static boolean[] visited ;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		Tc = Integer.parseInt(br.readLine());
		
		for( int tc = 1; tc<=Tc; tc++) {
			
			st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken()); // 정점 수 
			M = Integer.parseInt(st.nextToken()); // 간선 수 
			answer =  1; 
			
			start  = new ArrayList[N]; // 각 노드에 연결된 정점들
			visited = new boolean[N];  // 노드 방문 여부 
			
			for( int i=0; i<N; i++) {
				start[i] = new ArrayList<>();
			}
			
			
			// 1. arraylist에 연결된 정점 저장
			for( int i=0; i< M; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int from = Integer.parseInt(st.nextToken()) -1 ;  // 시작 정점
				int to = Integer.parseInt(st.nextToken()) - 1 ; // 도착 정점
				
				start[from].add(to);
				start[to].add(from);
			}
			
			// 2. 연결된 정점 모두 타고 들어가면서, dfs
			for( int Strt=0; Strt< N; Strt++) {
				visited[Strt] = true;
				dfs(Strt, 1, 0);
				visited[Strt] = false;
				
			}
			// 2-1. 
			
			// 3. 가장 depth 긴것,
			
			System.out.println("#"+tc+" "+answer);
		}
	}
	private static void dfs(int startNode, int step, int depth) {
		answer = Math.max( step , answer);
		
		// base rule
		if ( depth == N ) return;
		
		// 연결된 노드 타고 들어가자.
		for( int to = 0; to< start[startNode].size(); to++) {
			
			int target = start[startNode].get(to);
			if ( visited[ target ] ) continue; // 방문한 곳이면 가지말고
			
			// 처음 보는 곳이면
			visited[ target ]  = true; // 방문처리하고
			dfs( target, step+1, depth+1); // dfs
			visited[ target ] = false;

		}
	}
}