1389 - 케빈 베이컨의 6단계 법칙

• 난이도: 실버 1
• 날짜: 2023년 2월 24일
• 상태: Correct/Retry
• 추가 검토 여부: Yes
• 알고리즘 : BFS, Graph, 다익스트라 알고리즘, 플로이드 워셜 알고리즘

solution

• 1260번 문제와 마찬가지로 chat GPT의 코드를 이용하여 학습했다. chat GPT의 코드를 기반으로 문제의 조건에 맞게 일부 수정하여 제출하였다.
• 다익스트라 알고리즘의 구현은 BFS와 유사한 방식으로 구현되었다. 노드를 이동해 가면서 해당 노드의 인접 노드에 대해 정해진 규칙에 따라(다익스트라 알고리즘에서는 가장 시작 노드로부터weight의 합이 가장 적은 노드부터 탐색한다.) 탐색하고, 이를 priority queue에 삽입하여 모든 노드에 대한 연산이 끝날 때까지 반복한다.
• BFS와 구현 상의 차이점으로는, BFS는 visited벡터 컨테이너를 사용하여 방문한 노드인지의 여부를 확인해 모든 노드가 방문되었을 경우 반복문이 끝나는 형식으로 구현되어 있지만, 다익스트라 알고리즘의 경우 노드가 중복해서 queue에 들어갈 수 있다는 점이 가장 큰 차이점이다. 다익스트라 알고리즘에서 노드가 중복해서 queue에 들어가더라도(인접 리스트의 특성상 한번 연산한 노드에 대해서 다시 호출이 되는 구조이다.) 전체 거리가 더 적지 않다면 queue에 삽입하지 않기 때문에 반복문의 탈출이 가능하다.
• 다음은 기본적인 다익스트라 알고리즘이다.
  1. 출발 노드를 설정한다.
  2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
  3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
  4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
  5. 3~4를 반복한다.(모든 노드가 방문 처리되었을 때까지)
• 다음은 내 코드의 다익스트라 알고리즘의 작동 방식이다.
  1. start노드에 대한 dist배열 초기화 및 priority queue로의 삽입
  2. start노드의 인접 리스트를 참조하여 거리값 갱신, 거리값이 dist행렬의 값보다 작다면 초기화하고 priority queue로 push한다.
  3. push한 start노드의 인접 리스트에 있는 노드가 queue에서 pop되면서 2를 반복해서 수행한다. 이 과정은 priority queue가 empty가 아니라면 계쏙해서 반복된다.
• 본 문제에서는 노드 간 weight값이 1이라고 생각할 수 있으므로 모든 비용을 1로 처리했다.
• 본 코드에서 priority queue컨테이너에 들어가는 pair<int, int>는 first가 start로부터 현재 노드까지의 이동 비용이고, second가 인접 노드의 노드 번호를 의미한다.
  • 이 부분의 구현은 chat GPT의 구현이었는데, 사실 어떤 의도로 이러한 코딩을 했는지는 잘 모르겠다. 아마 인접 노드의 번호가 곧 가중치를 의미하는 상황인 것으로 추측된다. 본 문제에서 모든 가중치는 1로 통일되기 때문에 코드를 수정하여 노드 번호의 의미만 가지도록 하였다.
• 나는 이 문제를 다익스트라 알고리즘을 사용하여 해결하였다. 하지만 가중치가 1로 통일되어 있는 상황이기 때문에 BFS알고리즘으로도 충분히 해결 가능하다. 또한 백준 카테고리 상으로는 플로이드-워셜 알고리즘을 사용해서도 해결 가능하다. 추후에 시도해 볼 것. (기본적으로 그래프 상에서 두 정점 사이의 최소 거리를 구하는 알고리즘이니 당연하다…)

code

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int INF = INT_MAX;

vector<pair<int, int>> adj[10001];

void dijkstra(int start, int ** dist)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0,start});
    dist[start][start] = 0;

    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();

        for(auto v : adj[u])
        {
            int w = v.first;
            int weight = v.second;
            if(dist[start][u] + 1 < dist[start][w])
            {
                dist[start][w] = dist[start][u] + 1;
                pq.push({dist[start][w], w});
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    int ** dist = new int*[n+1];
    for(int i = 0; i < n+1; i++)
        dist[i] = new int[n+1];
    for(int i = 0; i < n+1; i++)
    {
        for(int j = 0; j < n+1; j++)
            dist[i][j] = INF;
    }
    for(int i = 0; i < m; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back({v, 1});
        adj[v].push_back({u, 1});
    }

    for(int i = 1; i <= n; i++)
        dijkstra(i, dist);

    int * sum = new int[n+1];
    for(int i = 0; i < n+1; i++)
        sum[i] = 0;
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            sum[i] += dist[i][j];
        }
    }
    int idx;
    int min = 99999;
    for(int i = 1; i <= n; i++)
    {
        if(min > sum[i])
        {
            min = sum[i];
            idx = i;
        }
    }
    cout << idx << endl;

    return 0;
}

ref

1389번: 케빈 베이컨의 6단계 법칙

23. 다익스트라(Dijkstra) 알고리즘