문제

---

코드

---

import java.util.*;
import java.io.*;

@SuppressWarnings("unchecked")
class Solution {
	static int N;
	static int M;
	static int max;
	static List<Integer>[] adjList;
	static boolean[] visited;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); // 정점의 개수
			M = Integer.parseInt(st.nextToken()); // 간선의 개수
			max = 0; // 최대값
			adjList = new List[N + 1]; // 인접 그래프
			for (int i = 1; i < N + 1; i++) {
				adjList[i] = new ArrayList<>();
			}
			visited = new boolean[N + 1];

			for (int i = 0; i < M; i++) {
				st = new StringTokenizer(br.readLine());
				int from = Integer.parseInt(st.nextToken());
				int to = Integer.parseInt(st.nextToken());

				// 무방향
				adjList[from].add(to);
				adjList[to].add(from);
			}

			for (int i = 1; i <= N; i++) {
				visited[i] = true;
				dfs(i, 1);
				visited[i] = false;
			}
			sb.append(String.format("#%d %d\n", t+1, max));
		}
		System.out.println(sb);
	}

	static void dfs(int vertex, int distance) {
		max = Math.max(distance, max);

		for (int adj : adjList[vertex]) {
			if (!visited[adj]) {
				visited[adj] = true;
				dfs(adj, distance + 1);
				visited[adj] = false;
			}
		}
	}
}

문제 이해

---

• 각 Test케이스마다 정점의 개수와 간선의 개수가 주어진다.
• 그 후 각 정점이 1 2이런식의 입력이 주어진다. 이 말은 1과 2사이에 간선이 존재한다는 의미이다.
• 이때 정점의 개수를 경로의 길이라고 할 때, 그 최대값을 구하면 된다.

풀이 방법

---

• 전형적인 dfs문제와 비슷하면서 백트래킹이 필요하다.
• 우선 인접리스트를 List[N+1]로 초기화해준다.
• 이때 각 간선은 무방향이기 때문에 간선을 추가할 때 from -> to, to -> from두 번 넣어주어야 한다.
• 그후 for문을 돌며 dfs를 수행한다.
• 이때 visted배열을 true로 바꿨다가 해당 정점에서의 dfs 탐색이 끝나고 나면 반드시 다시 false로 초기화해주어야 한다.
• dfs내부에서는 매호출마다 distance를 max값과 비교하여 항상 최대값을 유지한다.
• 인접리스트를 통해 해당 정점과 인접한 정점을 탐색한다. 만약 방문하지 않은 정점이라면 visited를 true로 변경한 후 dfs를 수행한다. 마찬가지로 모두 수행한 후 빠져나오고 나면 다시 visited를 false로 변경해주어야 된다.

핵심 포인트

---

• 시작정점이 정해져있지 않다. 대신 모든 정점에 대해서 모든 경로에 대한 길이를 구해야 하기 때문에 외부에서 for문으로 모든 정점에 대해서 dfs탐색을 진행해야 한다.
• dfs를 빠져나온다면 반드시 visited배열을 false로 초기화해주어야 한다. 그래야 다음 탐색에서 다시 새롭게 visted배열을 사용할 수 있게 된다.

보완할 점 / 느낀 점

---

• 이러한 그래프 문제를 오랜만에 풀어서 좀 헷갈렸었다.
• 시작정점점을 0으로 하는, 약간 standard느낌의 dfs코드는 기억이 났으나 모든 정점에 대해서 길이를 탐색해야되는 로직이 생각나지 않아 문제를 찾아봤었다.
• 그래도 몇번 백트래킹 문제를 풀어봐서 금방 이해할 수 있었고, 하루가 지난후 다시 풀었을 때는 혼자서 풀 수 있었다.

참고자료

---