2021.12.02 TIL

그래프 구조

그래프 구조를 알아보기위한 배열 선언이다. 모든 spot을 방문하는 logic을 만들기 위해서

visited라는 방문 여부를 표시하는 boolean 배열을 만든다. 방문하면 visited의 방문된 스팟의 요소가 true가 된다. visited[]가 false인 spot의 index, i 를 정해 for문 안에서 재귀호출을 한다. 3에서 부터 시작하게 되면,
visited[3] = true; print( "visit : 3") ;
i=2, visit( 2, visited, map)
visited[2] = true; print( "visit : 2" );
와 같이 작동하며 재귀호출을 통해 0번 spot까지 방문한 후, 1번spot을 방문 하고 나서 1에서 더이상 관계가 있는 spot이 없어 해당 for문이 종료되고 다시 i=0 인 for문으로 돌아가 4번 spot을 방문하고 visited[] 의 모든 요소가 true 가 돼 함수가 종료된다.

BFS (Breadth-First Search)
넓이 우선 탐색 이라는 뜻으로 queue 에 추가된 spot에 방문 후, queue에 추가/제거를 반복하며서 모든 spot에 방문하게 되는 식으로 코드를 짤 것이다.
먼저 다음과 같은 배열을 선언하고,

visit 을 정의한다. visit에는 방문 여부를 표시하는 visited, 대기열로 사용할 List인 queue가 멤버변수로 사용된다. for문을 통해 방문되지 않은 spot을 찾아 차례대로 방문하게 되고, 대기열에 해당 spot들을 추가한다. 추가된 spot 들은 while문의 조건이 만족되기 전까지 반복되며 방문된다.

DFS (Depth-First Search)
이동하고 해당 위치에서 다시 이동하는 형태의 검색으로 최단지점을 찾는데 이용한다.

spot간 거리에 가중치가 있는 배열을 선언한다. 갈수 있는 최단거리를 찾는 알고리즘을 만들기 위해서

visit함수를 정의한다. 최소값 min을 배열 가중치에 비해 상당히 큰 값으로 설정해두고 idx_min은 배열이 가질 수 없는 index 값인 음수로 설정한다. 그리고 출발 spot으로부터 가장 가까운 spot을 찾아내 방문하게 된다. 그 후 재귀호출을 통해 spot들을 모두 방문하기 전까지 반복하여 visit 이 실행된다. 위와 같은 코드를 짰을 때는, 더 이상 직접 방문이 안될 경우는 모든 spot이 방문되지 않고 코드가 종료될 가능성이 있다. 이에 대한 해결책으로는 BFS와 같은 순서열 배열을 만들어 순차적으로 방문하게 하는 방법이 있다.