Treejin's Note

문제 설명

 가중치가 없는 무방향 그래프에서의 최장 경로를 계산하는 문제로, 쉽게 말해서 중복되지 않고 가장 많은 정점을 연결하는 경우를 찾으면 되는 문제이다.

문제 풀이

  그래프의 서로 연결된 간선을 타고 최장 거리를 구하는 문제이므로 DFS를 이용했다. 이때 시작점을 바꾸어가면서 DFS를 수행하면 모든 정점의 경우에 따른 최장 거리를 구할 수 있고, 그중 가장 먼 거리의 값을 출력하면 된다.

 주어지는 간선의 정보는 인접리스트의 형태로 저장하였다. 이때, 문제의 입력에서 정점의 개수(N)가 10개 이하라고 설명되어 있었기 때문에 int형 변수의 비트 마스킹을 통해 간선 정보를 저장하면 간편하겠다고 생각했다. 이와 함께 DFS를 수행할 때에도 방문처리를 수행할 때 파라미터로 비트 마스킹된 방문 정보를 전달하였다.

문제 풀이 코드

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

public class _2814_최장경로 {
	static int N,M,arr[],max;
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(in.readLine());
		for (int tc = 1; tc <= T; ++tc) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			arr = new int [N];
			max = 1;
			for (int i = 0; i < M; ++i) {
				st = new StringTokenizer(in.readLine());
				int x = Integer.parseInt(st.nextToken())-1;
				int y = Integer.parseInt(st.nextToken())-1;
				arr[x] |= (1<<y);
				arr[y] |= (1<<x);
			}
			
			for(int i = 0; i<N;++i) {	//돌아가면서 시작점 선택
				dfs(i,1<<i,1);
			}
			
			System.out.println("#"+tc+" "+max);
			
		}
	}
	
	private static void dfs(int num,int visited, int count) {
		for(int i = 0 ; i<N;++i) {
			if((arr[num] &(1<<i))>0 && (visited & (1<<i)) == 0) {	//간선이 있고 방문하지 않았을 때
				dfs(i,visited|(1<<i),count+1);
			}
		}
		max = Math.max(count, max);
	}
}

더하기

 이 문제에서는 주어지는 정점과 간선의 개수가 적었기 때문에 완탐으로 패스했지만, 정점과 간선의 개수가 많아지면 시간이 오래 소요된다. 이에 관해서는 메모이제이션을 통해 해결할 수 있다.

=> 방문체크 상태가 같으면서 같은 정점에 관해 수행할 때, 이미 기록된 값이 있다면 그 뒤의 흐름의 방식은 같으므로  기록된 값을 이용함으로써 더 계산하지 않는다.