[Algorithm] Graph의 두 접점 간 연결 관계 탐색

🎯 목표 : 인접 행렬과 접점이 주어졌을때, 두 접점간의 연결 관계가 있는 지 여부를 반환하는 알고리즘 작성

📒 Vertex to Vertex Find Direction

📌 해결할 문제

• 인자로 주어진 인접 행렬과 두 접점을 활용하여 두 접점간 연결 관계 여부를 반환

📌 알고리즘

• 인접 행렬을 가진 2차원 배열과 진출 접점과 진입 점점이 인자로 주어진다.
• 재귀 호출을 이용하여 방문한 지점을 체크하며 탐색한다.
• 진출 접점과 진입 점점이 같다면 두 점점의 연결 관계가 있으므로 true를 반환한다.(재귀 호출의 도착점)
• 진출 접점과 관계가 있는 점점들을 찾기 위해 진출 접점의 요소를 가진 1차원 배열을 순회한다.
• 관계가 있는 접점을 찾았다면 해당 접점의 방문 체크를 하기위해 값을 0으로 변경한다.
• 체크된 행렬 2차원 배열과 관계가 있는 접점, 진입 점점을 인자로 갖는 재귀 호출을 실행한다.

📌 알고리즘 구현

public class DirectionsTest{
	public static void main(String[] args) {
            int[][] input = new int[][]
                {
                        {0, 1, 0, 0, 0},
                        {0, 0, 0, 1, 0},
                        {0, 1, 0, 0, 0},
                        {0, 1, 1, 0, 0},
                        {1, 1, 1, 1, 0}
                };
        DataStructureQuiz2 a = new DataStructureQuiz2();
        // input 인접 행렬을 받아 vertex 1 - 4에 도달할수 있는지 여부 확인
        System.out.println(a.findDirections(input,1,4));

    }
    public boolean findDirections(int[][] matrix, int from, int to) {
    	int[][] compareArr = new int[matrix.length][];
    	for(int i=0; i< matrix.length; i++) compareArr[i]
            =Arrays.copyOf(matrix[i],matrix[i].length);
    	if (from==to) return true;
    	for (int i=0; i<compareArr[from].length; i++){
        	if(compareArr[from][i]==1){
            compareArr[from][i]=0;
            if(getDirections(compareArr,i,to)) return true;
        	}
    	}
    	return false;
	}
}

// 출력값
// false