/
알고리즘 : DFS
n에서 k까지 최단 거리 구하기
/
public class JmTest004 {
static int T; //테스트케이스 갯수
static int V; //노드 갯수
static int E; //간선 갯수
static int [][] adj; //인접행렬
static int [] visited; //방문배열
static int min; //최단거리 값
public static void main(String[] args) throws Exception{
System.setIn(new FileInputStream("JmTest002.txt"));
Scanner sc = new Scanner(System.in);
T = sc.nextInt(); //테스트케이스 갯수 입력
for(int tc=1; tc<=T; tc++)
{
V = sc.nextInt(); //노드 갯수 입력
E = sc.nextInt(); //간선 갯수 입력
adj = new int [V+1][V+1];
visited = new int [V+1];
min = Integer.MAX_VALUE;
for(int i=1; i<=E; i++)
{
int n1 = sc.nextInt();
int n2 = sc.nextInt();
adj [n1][n2] = 1;
}
sc.close();
dfs(1, 4, 0);
System.out.println(min);
}
}
public static void dfs(int n, int k, int e)
{
if(n == k)
{
if(min > e)
{
min = e;
}
}
else if(min <= e)
{
return;
}
else
{
visited[n] = 1; //방문표시
for(int i=1; i<=V; i++)
{
if(adj[n][i] == 1 && visited[i] == 0)
{
dfs(i, k, e+1);
}
}
visited[n] = 0; //방문표시
}
}
import java.io.FileInputStream; import java.util.Scanner;
/ 알고리즘 : DFS n에서 k까지 최단 거리 구하기 / public class JmTest004 { static int T; //테스트케이스 갯수 static int V; //노드 갯수 static int E; //간선 갯수 static int [][] adj; //인접행렬 static int [] visited; //방문배열 static int min; //최단거리 값
}