[SWEA - 2814] D3 - 최장경로

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB&categoryId=AV7GOPPaAeMDFAXB&categoryType=CODE

SW Expert Academy

1. 유형

dfs, 인접리스트

 

2. 풀이

• 연결리스트를 만든다
• visit배열로 방문지점을 체크하며 재귀를 돌린다

3. 코드

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

public class Main {
	static int T, N, M;
	static boolean visit[];
	static int res = 0;
	static ArrayList<Integer> list[];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		T = Integer.valueOf(st.nextToken());
		for (int tc = 1; tc <= T; tc++) {
			res=0;
			st = new StringTokenizer(in.readLine(), " ");
			N = Integer.valueOf(st.nextToken());
			M = Integer.valueOf(st.nextToken());
			list = new ArrayList[N+1];
			for (int i = 0; i < N+1; i++) {
				list[i] = new ArrayList<>();
			}
			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				int u = Integer.valueOf(st.nextToken());
				int v = Integer.valueOf(st.nextToken());
				list[u].add(v);
				list[v].add(u);
			}
			for (int i = 1; i <= N; i++) {
				visit = new boolean[N+1];
				dfs(i, 1);
			}
			System.out.println("#"+tc+" "+res);
		}
	}

	static void dfs(int from, int d) {
		visit[from] = true;
		res = res < d ? d : res;
		// 인접리스트 탐색하기
		for (int to : list[from]) {
			if (!visit[to]) {
				dfs(to, d+1);
				visit[to] = false;
			}
		}
	}
}

4. 느낀점

 

맨날 bfs만 풀다가 오랜만에 재귀를 풀었더니

 

방향은 빨리 잡았지만, 방문 해제하는걸 까먹어서 조금 시간이 걸린 문제다.

 

복습을 철저히 해야겠다.