🍀Graph Search Algorithm
Graph Traversal
DFS나 BFS 둘 다 모든 정점을 방문한다
🍒BFS(Breadth-First Search)
너비(breadth) 우선 탐색
인접한 정점부터 순회
Queue를 사용하여 구현(FIFO)
root.add->인접 nodeA~C.add ->
root(nodeA).add -> nodeA-1~3 ...
최단경로 탐색에 유리(가까운 곳부터 순회하니까)
메모리 사용이 큼(방문함 모든 정점을 저장해야 하는경우)
그래프가 크면(정점이 많으면) 성능이 떨어짐
방문여부를 체크하는 자료구조를 사용해야 함(무한루프 방지)
정점을 꺼낼 때는 큐 비었는지 확인하기
🥝DFS(Depth-First Search)
깊이(Depth) 우선 탐색
스택 혹은 재귀를 이용하여 구현
한 분기에서 다음분기로 넘어가기 전에 해당 분기를 완벽하게 탐색
그래프 내의 순환구조를 고려하여 방문한 정점을 재방문하지 않도록 해야 함
도달 정점이 있어야 함(무한루프 방지)
찾은 길이 최단 경로가 아닐 수도 있다
경로의 특징을 저장할 때 사용
목표 정점이 깊은 단계에 있으면 보다 빨리 구할 수 있다
그래프가 정말 크다면 DFS를 고려할 것(목표 경로 정점만 저장)
🍀실전문제
인접 행렬 생성하기
문제가 이해도 잘 안되고 어려워서 대충 이렇게하면 되지 않을까?라는 반복문을 작성후 요소를 한 두개 넣어 머리속에서 돌려 보았다
대입관련 코드는 잘 작성 한 것 같은데 OutOfBoundsException 오류가 났다
입력받은 간선목록 배열 길이가 정점의 경우의 수와 같을 거라는 오판을 했다
수정전 코드 int[][] result = new int[arr.length][arr.length]; (arr는 간선들의 목록이 담긴 배열)
-> 제대로된 값을 구하기 위해선 정점의 값중 가장 큰 값을 사용해야 했다
-> for문으로 배열을 순회 후 max값을 찾아 int[][] result = new int[max + 1][max + 1];
인접 행렬 길찾기
public boolean getDirections(int[][] matrix, int from, int to) {
int[][] copyMatrix = new int[matrix.length][];
for(int i = 0; i < matrix.length; i++) {
copyMatrix[i] = Arrays.copyOf(matrix[i], matrix[i].length);
}
if(from == to) return true;
for(int i = 0; i < copyMatrix[from].length; i++) { //from 번째 배열 순회
if(copyMatrix[from][i] == 1) { //해당배열에 1이 있으면(순회하지 않았다면)
copyMatrix[from][i] = 0; //순회했음을 표시(무한루프방지)
if(getDirections(copyMatrix, i, to)) {
return true; //if(from == to)
}
}
}
return false;
}재귀함수를 써야될것 같은 느낌은 들어서 while, for, if문으로 이리저리 코드를 작성했다
입력 배열에서 조건문에 1이 나올경우 from[][i]에서 i를 from에 대입시켜 재귀로 순회를 해야한다 까지는 알겠는데 1이 두번 나올경우 어떻게 반복적으로 순회시키는지 도통 감이 오질 않았다
->입력받은 배열을 그대로 사용하는게 아닌 입력받은 복사해서 조건문을 실행한 요소를 1->0으로 처리하는 방법이었다
이후 from == to가 true인 경우가 왜 경로가 존재한다 보는건지 이해가 안되서 한참을 고민했다
->재귀로i값을 from에 넣음으로 순회중인 배열(시작정점)from의 인덱스(도착정점)i와 인접관계에 있는 것이며, 도착지점이 인접하다는건i = to로 표현됨으로 재귀함수의 결과값으로 from = to가 성립하는 거였다
마지막은 고민하다 지쳐서 누워서 눈감고 생각하다 해결이 났다;;
중간에 벨로그가 터져서 메모장에 저장해 놨다 다음날 올렸다
아침부터 온몸이 쑤시고 허리가 너무 아파서 의자에 앉아있기가 힘들었다
잠깐 누워있는데 내가 이제 컴퓨터도 못하는 체력이 됬나 심란해졌다
나중에 알고보니 열나고 몸살이 나서 몸이 아픈거였다. 다행이다
