[SWEA] 2814 최장경로 - Java

최장경로 구하기 ➔ DFS

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

SW Expert Academy

---

📍 고려해야할 점

• 최단경로가 아닌 최장경로를 구해야한다.
• 인접리스트 또는 2차원 배열을 활용한다. 
• 각 정점마다 방문해서 최장경로를 구해야한다.
  • DFS로 진행하고 방문했던 곳을 표시하고, 복구시켜야한다. 

---

✨ BFS로 풀면 안되는 이유

BFS는 시작 노드에서부터 거리에 따라 단계적으로 탐색을 진행하며, 한 노드에서 다음 노드로 이동할 때 이전에 방문한 노드를 다시 방문하지 않는 특성을 가지고 있다. 그러므로 모든 경로를 고려하여 최장경로를 탐색하는 문제에는 적합하지 않으며 각 노드를 최단경로로 방문하는 문제에서 적합하다. 

 

 

🕹️ 풀이과정

1. 정점과 간선의 정보를 2차원배열 또는 인접리스트를 활용하여 저장한다.
2. 각 정점마다 DFS 함수를 호출하여 최장경로를 구한다.
3. 시작 노드마다 최대 이동거리가 다르기 때문에 모든 정점에서 탐색해야 한다. ➔ visit 배열 false로 복구 필요 !

 

 

👩‍💻 전체 코드 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class SWEA_2814_최장경로 {
	
	static int[][] arr;
	static boolean[] visit;
	static int n,m,max;
	
	static void dfs(int cnt, int x) {
		visit[x]=true;
		
		for(int i=1; i<=n; i++) {
        	// 이미 방문한 곳은 탐색할 필요 없다.
			if(arr[x][i]==1 && !visit[i]) {
				dfs(cnt+1, i);
				visit[i] = false;
			}
		}
		max = Math.max(max, cnt);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		
		for(int t=1; t<=T; t++) {
			
			st = new StringTokenizer(br.readLine());
			
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			
			arr = new int[n+1][n+1];
			visit = new boolean[n+1];
			
			for(int i=0; i<m; i++) {
				st = new StringTokenizer(br.readLine());
				
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				
				arr[x][y]=1;
				arr[y][x]=1;
			}

			for(int i=1; i<=n; i++) {
				dfs(1, i);
                visit[i] =false;
			}
			bw.write("#" + t+ " " + max + "\n");
		}
		bw.flush();
		bw.close();
	}
}