14. 다익스트라(Dijkstra) 알고리즘 응용편

1. 문제

 아래 문제를 5시간 안에 푸시오. (저작권 문제로 스크린샷 없애고, 글로 유사 문제로 변형)

  

각, 노드의 이름이 숫자가 아닌 문자열로 주어질 때의 문제이다.

예를 들어

GRB ADD 5란 입력은 GRB란 노드와 ADD란 노드의 거리는 5를 의미한다.

입력은 시작 노드와 종료 노드를 문자열로 입력한다.

실행 후 출력 방식은

시작 노드 -> 엣지 길이 -> 경유 노드 -> 엣지 길이 -> ... -> 끝 노드

이다.

다음에 데이터가 주어질 때, 

GRB ADD 5

GRB CDA 9

ADD CDA 1

ADD DFA 4

CDA ERD 5

CDA FRA 6

EDG DFA 3

DFA GONG 8

FRA GONG 7

시작노드와 끝 노드를 입력하면 출력하는 코드를 작성하시오.

아래 코드는 연결리스트 기반 Hash와 다익스트라 알고리즘의 조합으로 풀어냈다.

2. 코드

2-1) 구조체 선언

2-2) 해쉬 선언

2-3) 메인

2-4) 해쉬 함수들

2-5) 파일 해석 알고리즘

2-6) 다익스트라 알고리즘 

2-7) 출력

3. 해설

 이번 문제는 단순히 다익스트라 알고리즘만 필요한게 아닌 해쉬 기법과 파일 입출력 기법을 적절히 조정해야하는 문제다.

해쉬 기법은 정점의 이름과 번호를 매칭시키기 위해 사용하였다. 해쉬 키값은 각 정점 이름의 알파벳 아스키코드를 합친 후 

1차 해쉬 함수인 소수 17로 나눈 나머지이다. 그리고 위의 선언부의 Define 값에 따라 전체 계산 가능한 크기를 설정할 수

있다. 굳이 2차 해쉬 함수를 사용하지 않은 이유는 현재 데이터가 크지 않기 때문이다. 데이터가 커져서 만약 똑같은 해쉬

키값이 많이 등장한다면 2차 해쉬 함수를 고려해야할 것이다. 그리고 현재 코드는 기존에 잡아둔 최대 크기만큼 계산할 수

있으므로 한계가 있다. 이 한계를 수정하기 위해서는 크기에 따라 그래프의 Adj부분을 가변 배열로서 변한게 한다면 

가능하다. 하지만 그만큼 시간 소요가 된다. 이 방법이 현재 내 수준으로 가장 깔끔하고 빠르게 풀릴 것이라 생각한 방법이다.

더 좋은 방법들이 훨씬 많겠지만 추후에 새롭게 더 빠르게 할 수 있다면 다시 작성한다.

 그 당시의 나로서는 5시간에 풀어낸다는게 정말 엄두가 안났지만 공부하다보니 이제는 알겠다. 충분히 풀어낼 수 있는

문제였다는걸. 역시 모든 문제는 내 실력이다. 실력을 쌓자. 쌓다보면 날 알아주는 기업이 나타나겠지.

다음은 출력파일과 예시 그래프 데이터, 그리고 전체 코드이다. 혹시라도 도움이 될 수 있는 사람들을 위해.

[코딩인터뷰퀘스쳔].exe

graph.txt

Source.cpp