[백준 1238번] 파티

https://www.acmicpc.net/problem/1238

1238번: 파티

풀이) 

한 정점에서 다른 한개의 정점이 아니기에 플로이드 와샬로 풀어야 한다고 생각했다. 무한대로 초기화시켜놓고 거쳐가는 모든 경로를 확인하면서 최단경로를 확인하면 해결될 것이라 생각했는데, 시간초과가 났다. O(N^3)이여서 1000일경우 10억이 되기에 안된다는 생각을 그때 깨달았다. 하지만 질문검색에서 무한대인경우를 탐색을 진행하지 않는 방식으로 잘 가지치기를 하면 통과한다는 글이 있었고 해결할 수 있었다. 물론 운이 좋았다고 생각했고, 다익스트라 알고리즘을 이용해서 다시 한번 풀어보았다. 다익스트라 알고리즘 같은 경우 시작점 -> 마을 + 마을 -> 시작점의 최단경로가 가장 짧은 곳은 구하는 방식으로 접근하였다. 

 

1. 플로이드 와샬을 이용한 풀이 

#include <iostream>
using namespace std;

int N, M, X, ans = 0;
int arr[1001][1001];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N >> M >> X;
	
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
      	    arr[i][j] = 2e8;

    for (int i = 0; i < M; i++)
    {
        int s, e, c;
        cin >> s >> e >> c;
        arr[s][e] = c;
    }

    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            if (arr[i][k] == 2e8)
                continue;
            for (int j = 1; j <= N; j++)
                arr[i][j] = min(arr[i][j], arr[i][k] + arr[k][j]);
        }
    }
    for (int i = 1; i <= N; i++)
        if (i != X && arr[i][X] != 2e8 && arr[X][i] != 2e8)
            ans = max(ans, arr[i][X] + arr[X][i]);

    cout << ans << "\n";

    return (0);
}

2. 다익스트라 알고리즘을 이용한 풀이

#include <iostream>
#define INF 2e8
using namespace std;

int N, M, X, x, y, z, cnt = 0, ans = -1;
int cost[1001][1001], cost_[1001][1001], result[2][1001], visited[1001];

int findMin(int start)
{
    int tmp = INF, idx = 0;
    for (int i = 1; i <= N; i++)
	{
        if (!visited[i] && result[cnt][i] < tmp)
		{
            tmp = result[cnt][i];
            idx = i;
        }
    }
    visited[idx] = 1;
    return (idx);
}

void dijkstra(int start)
{
    for (int i = 1; i <= N; i++)
	{
		result[cnt][i] = INF;
        visited[i] = 0;
    }
	result[cnt][start] = 0;
    for (int i = 1; i <= N; i++)
	{
        int t = findMin(start);
        for (int j = 1; j <= N; j++)
		{
			if (cnt == 0 && cost[t][j] != 0 && result[cnt][t] + cost[t][j] < result[cnt][j])
				result[cnt][j] = result[cnt][t] + cost[t][j];
            else if (cnt == 1 && cost_[t][j] != 0 && result[cnt][t] + cost_[t][j] < result[cnt][j])
				result[cnt][j] = result[cnt][t] + cost_[t][j];
        }
    }
    cnt = 1;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

    cin >> N >> M >> X;
    for (int i = 1; i <= M; i++)
	{
        cin >> x >> y >> z;
        cost[x][y] = z;
        cost_[y][x] = z;
    }

    dijkstra(X);
    dijkstra(X);
    
    for (int i = 1; i <= N; i++)
        if (result[0][i] + result[1][i] > ans)
            ans = result[0][i] + result[1][i];
			
    cout << ans << "\n";
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!