연구활동 가는 길( 인접 행렬 풀이 )

1. 문제

2. 문제 분석

위는 SetDataLoadDataFromFile함수가 호출이 되면, 이차원배열g_Path에 cost가 저장이 된다.

cost값이 0이라는 의미를 2가지를 포함하고 있다.

1. 자기 자신에서 자기 자신으로 갈 때의 cost값은 0이다.

2. '길'을 갈 수가 없는 경우에 cost값은 0이다. (현재의 정점과의 연결이 안된 경우)

예를 들어서, g_Path[0][0] = 0 의 의미는 자기 자신에서 자기 자신으로 갈 때의 경우이다.

g_Path[1][2] = 0 의 의미는 1번 정점과 2번 정점은 서로 연결되지 않았다는 의미이다,

여기서, 탐색을 할 때 이차원 배열의 행과 열은 다음과 같다.

행 요소 = 현재의 정점

열 요소 = 현재의 정점과 연결된 다음 정점

이를 토대로 다시 설명하면 이차원 배열의 값이 0인 경우는

1. 현재의 정점에서 현재의 정점으로 되돌아 가는 경우

2. 현재의 정점과 연결된 다음 정점이 아닌 경우

 

위의 인접행렬을 보면, 0번 정점을 시작으로 탐색을 시작한다. 배열의 인덱스는 0-base이다.

아래의 그림은 탐색을 하는 함수를 재귀함수로 구현했을 때, 그 호출 스택이다.

파란색 숫자는 호출 순서를 의미한다.

정점의 개수가 7개이므로, 최종적으로 탐색할 마지막 정점은 6번 정점이다.

그리고 이 방식에는 메모이제이션 기법을 통해서 거쳐온 정점들을 기록하도록 한다.

이미 거쳐온 정점이 있다면 다시 그 정점으로 되돌아가지 못하도록 한다.

그리고 위의 함수 호출 스택 5번과 6번을 동시에 해석해보면 다음과 같다.

3번 정점과 5번 정점이 서로 연결되어 있어서 현재의 정점3에서 정점5로 탐색을 한다.

그리고 5번 정점과 연결된 정점이 6번 정점이며 이는 마지막 정점임을 의미하게 된다.

즉, 탐색 종료가 된다. 5번 정점을 시작으로 모든 탐색이 끝났으므로, 기록된 5번 정점을 다시 기록 해제한다.

그러면 다시 호출 스택 5번으로 이동이 되며 이는 3번 정점을 시작으로 마지막 정점까지의 탐색이 모두 완료됨을

의미하므로, 기존에 기록된 3번 정점을 다시 기록하지 않은 상태로 되돌려 놓는다. 

이와 같은 기법을 백트래킹이라고 한다.

위 탐색을 기반으로 구현한 함수는 아래와 같다.

3. 구현

아래는 파일에 있는 내용이다.

프로그램 실행결과

4. 소스 파일 & 텍스트 파일

main.c

0.00MB

연구활동 가는길.txt

0.00MB

5. 보다 연산량을 줄일 수 있는 방법

아래와 같이 탐색한 정점까지의 누적비용이 그 이전에 구한 비용보다 크다면

더 이상 탐색할 이유가 없다. 우리가 구하려는 것은 최소 비용이기 때문이다.

 6. 소스 파일

main.c

0.00MB

7. 다른 문제 풀이와 소스 파일

main.c

0.00MB