[SWEA] 2814 : 최장경로

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

SW Expert Academy

인접리스트로 구현해봄.

 

내 코드

메모리 : 18448 KB

시간 : 113 ms

코드길이 : 1842 B

 

[내 코드]

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

public class Solution {
	static int N;
	static int M;
	static ArrayList<Integer>[] list;
	static int result;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T= Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			list = new ArrayList[N + 1];
			boolean[] isVisited = new boolean[N + 1];
			result = 0;
			
			if(M == 0 || M == 1) {
				sb.append(M + 1).append('\n');
				continue;
			}
			
			//인접리스트 초기화** 필수
			for(int n = 0; n < N + 1; n++) {
				list[n] = new ArrayList<Integer>();
			}
			
			for(int m = 0; m < M; m++) {
				st = new StringTokenizer(br.readLine());
				int node1 = Integer.parseInt(st.nextToken());
				int node2 = Integer.parseInt(st.nextToken());
				list[node1].add(node2);
				list[node2].add(node1);
			}
			
			for(int i = 1; i <= N; i++) {
				isVisited[i] = true;
				search(i, 1, isVisited);
				isVisited[i] = false;
			}
			
			sb.append(result).append('\n');
		}
		System.out.print(sb);
	}
	public static void search(int node, int length, boolean[] isVisited) {
		for(int i = 0; i < list[node].size(); i++) {
			int nextNode = list[node].get(i);
			if(!isVisited[nextNode]) {
				isVisited[nextNode] = true;
				search(nextNode, length + 1, isVisited);
				isVisited[nextNode] = false;
			}
		}
		
		result = Math.max(result, length);
		
	}

}