문제
주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.
입력
인자 1: matrix
- Array 타입을 요소로 갖는 인접 행렬이 담긴 2차원 배열
인자 2: from
- int 타입의 시작 정점
인자 3: to
- int 타입의 도착 정점
출력
- boolean 타입을 리턴해야 합니다.
import java.util.LinkedList;
import java.util.Queue;
public class AdjacentFindRoot {
public static void main(String[] args) {
/*
- 인접 행렬에서 한 정점으로 부터 다른 정점으로 이어지는 길이 존재하는지 반환
- 입력 : 2차원 배열, 시작정점, 도착정점
- 출력 : 시작정점에서 도착 정점으로 가는 길이 있으면 true 를 반환
*/
int[][] test = new int[][]{
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
boolean directions = getDirections(test, 1, 4);
System.out.println(directions);
}
public static boolean getDirections(int[][] matrix, int from, int to) {
Queue<Integer> queue = new LinkedList<>();
queue.add(from);
boolean[] visited = new boolean[matrix.length];
visited[from] = true;
while(queue.size() > 0){
int now = queue.poll();
if(now == to) return true;
for (int i = 0; i < matrix[now].length; i++) {
if (matrix[now][i] == 1 && !visited[i]) {
queue.add(i);
visited[i] = true;
}
}
}
return false;
}
}
'알고리즘' 카테고리의 다른 글
후위 표기식 (0) | 2022.09.25 |
---|---|
decryptCaesarCipher (0) | 2022.08.09 |
인접 행렬 생성하기 (0) | 2022.08.04 |
문자열에서 숫자 추출 알고리즘 (0) | 2022.08.01 |
동전 교환 알고리즘 (0) | 2022.07.30 |