BOJ 1238 파티

1238번: 파티 (acmicpc.net)

1238번: 파티

처음에는 문제를 잘못 이해해서 단순히 x번 집에서 다른 집으로 가는 최소 거리를 구하면 된다는 생각에 그래프의 정보로 들어오는 시작점과 도착점을 반대로 해 Node를 생성하는 방식을 채택했다.

 

그리고 결과를 보고 나서 문제를 다시 한 번 봤는데 알고보니 갔다가 다시 돌아오는 것이어서 방법을 바꿨다.

그런데 생각을 해보니 기존에 했던 방식은 우리가 2번으로 도착했다가 다시 돌아갈 수 있는 경로의 최소 거리인 것 같았다.

그래서 맨 처음 Node는 들어오는 값을 그대로 넣어서 알고리즘을 풀었고, 최소 거리 배열을 초기화한 후 거꾸로 넣은 Node들을 새로 넣어 다시 한 번 알고리즘을 통해 최소 거리를 도출해냈다.

 

그리고 그 거리들을 합해 그 중 최장 거리를 도출해서 정답을 받았다.

 

여기서 사용한 알고리즘은 다익스트라로 한 점에서 다른 점까지 가는 최단 거리를 구할 수 있는 알고리즘이다.

 

static void Dijkstra(int start, ArrayList<ArrayList<Info>> edge)
{
	int cost = 0;
    distance[start] = 0;
    PriorityQueue<Info> que = new PriorityQueue<>();
    que.add(new Info(start,0));
    while(!que.isEmpty())
    {
    	Info i = que.poll();
        int now = i.y;
        int dist = i.dist;
        if ( distance[now] < dist) { continue; }
        for ( int j = 0; j < edge.get(now).size(); j++)
        {
        	cost = dist + edge.get(now).get(j).dist;
            if ( cost < distance[edge.get(now).get(j).y])
            {
            	distance[edge.get(now).get(j).y] = cost;
                que.add(new Info(edge.get(now).get(j).y, cost));
             }
         }
     }
}

이게 기본 다익스트라 알고리즘을 자바로 구현한 것이다. 원래는 edge가 들어가지 않지만, 거꾸로 만든 edge를 새로운 ArrayList에 넣어줬으므로 인자로 들어갈 수 있도록 표현했다.

 

실제 알고리즘은 알고 있는 다익스트라와 다를 것이 없다. 

 

Dijkstra(x,edge);
for ( int i = 1; i <= n; i++)
{
	answer[i]+=distance[i];
}
Arrays.fill(distance, INF);
Dijkstra(x,edge2);
for ( int i = 1; i <= n; i++)
{
	answer[i]+=distance[i];
}

다익스트라를 활용해서 이런 방식으로 최장 거리를 계산하였다.

먼저 다익스트라를 정상으로 돌려서 2번에서 다른 집으로 갈 수 있는 최단 거리를 구한다.

그 뒤 시작점과 도착점을 뒤집은 edge2에서 다른 집에서 2번으로 갈 수 있는 최단 거리를 구하게 된다.

그 뒤 두 거리를 더해서 최장 거리를 구하면 끝이다.

 

우연한 아이디어를 통해서 문제를 풀었던 것이라서 가끔은 이런 실수들이 답을 도출해내는데 도움이 될 수 있다는 것을

깨닫게 된 순간이었다.