백준 1753 최단경로 (메모리초과)

 

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다

 

 

 

 

 

 

 

다익스트라 알고리즘 우선 기준점이 정해지면 그 기준점을 기준으로 각 정점까지의 최단거리를 계산하는 알고리즘.

기본 아이디어는 우선 각 정점간의 간선 정보를 받아서 기준점을 시작으로 다음 정점으로 이동하는 기준을 방문하지 않은 정점중에 최단거리를 가지고 있는 정점으로 한다.

따라서 기준점을 기준으로 각 정점까지의 최단 거리를 저장할 일차원 배열 d가 필요하고, 각 정점간의 간선 정보를 저장할 const 2차원 배열이 필요하다. 그리고 각 정점에 대해 방문 했는지를 표시할 visit 배열이 필요하다.

기준점을 시작으로 해서 방문하지 않은 정점중 최단 정점을 찾는 함수를 구현하여 그 인덱스를 반환시키고 그 함수로 이동한다. 이동이라는 것은 visit값이 true가 되었다는 뜻.

이동 한 뒤에 방문하지 않은 정점에 대해 즉 자신의 이전 정점들과 자신을 제외한 정점 중에 기준점을 기준으로 현재까지의 거리값 ( 기준점 자신에 대한 거리는 0일 것이며 이미 기준점은 visit가 되어있기 때문에 탐색하지 않음) 이 현재 이동된 정점까지의 거리값과 현재 정점에서 해당 정점까지의 거리값을 더한 값보다 크다면 이 값으로 바꿔준다. 그러면 d에 저장된 값이 업데이트가 된다.

이 과정을 반복 하여 기준점을 기준으로 각 정점까지의 최단 거리를 저장한 배열 d를 만들어낸다.

 

나는 2차원 배열로 이 문제를 풀었는데, 현재 메모리 문제를 해결하지 못하였다. 이를 해결하려면 배열을 쓰지않고 다익스트라를 구현해야 하는데 아직 아이디어가 없으므로,,, 다음에 다시 공부해 보기로 한다.

 

 

 

#include <iostream>
using namespace std;


 int V,E,K;
 int arr[20000][20000];

const int INF =1000000;


int getshort(int *d, int *visit)
{

int index;
int min = 1000000;

for(int i=0; i<V; i++)
{

if(!visit[i] && d[i]<min)
{
min=d[i];
index =i;
}

}

visit[index]=true;
return index;

}


void dijkstra(int start,int *d, int *visit)
{

visit[start] = true;

for(int i = 0; i<V; i++ )
{ 
   d[i] = arr[start][i];
}

d[start] = 0;

for(int i= 0 ; i<V-2; i++)
{
int current = getshort(d,visit);

for(int j =0; j<V; j++)
{
if(!visit[j])
{
if(d[current]+arr[current][j] < d[j] )
{

d[j] = d[current]+arr[current][j];
}
}
}

}



}


int main(void)
{



cin >> V >>E;
cin>>K;




      int d[V];
      int visit[V];


for(int i=0; i<V; i++)
 for(int j=0; j<V; j++)
  {
   arr[i][j] =INF;
  }

for(int i=0; i<E; i++)
{
int a,b,c;

cin >>a>>b>>c;

arr[a-1][b-1]=c;


}

dijkstra(K-1,d,visit);

for(int i =0; i<V; i++)
{

if(d[i] == INF)
{
cout<<"INF"<<endl;

}
else
{
cout<<d[i]<<endl;
}

}




}