[Algorithm]Baekjoon 1976번 : 여행 가자

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

1976번: 여행 가자

 
int n, m, input;
int adjArr[201][201];
int routes[1001]; 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    memset(adjArr, 0x3f, sizeof(adjArr));
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> adjArr[i][j];
            if (i != j && adjArr[i][j] == 0)
            {
                adjArr[i][j] = 0x3f3f3f3f;
            }
        }
    }
 
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                if (adjArr[i][j] > adjArr[i][k] + adjArr[k][j])
                {
                    adjArr[i][j] = adjArr[i][k] + adjArr[k][j];
                }
            }
        }
    }
 
    for (int i = 0; i < m; ++i)
    {
        cin >> routes[i];
    }
 
    for (int i = 0; i < m - 1; ++i)
    {
        if (adjArr[routes[i]][routes[i + 1]] == 0x3f3f3f3f)
        {
            cout << "NO";
            return 0;
        }
    }
 
    cout << "YES";
}

 

문제를 읽고 생각난 풀이법은 두가지였다.

플로이드와샬이랑 유니온파인드.

일단 플로이드와샬로 먼저 풀어봤다.

그냥 주어진 여행경로가 가능한지만 체크하면 되기 때문에, 플로이드와샬로 인접배열을 업데이트를 전부 해놓으면 쉽게 구할 수 있다.

다만, 시간복잡도가 n^3이라서 n값이 더 크면 효율은 안좋을 것이다.

 

그래서 유니온파인드도 오랜만에 감 익힐겸 풀어봤다.

말이 유니온파인드지 그냥 한번의 탐색동안 탐색되어지는 노드들의 부모를 똑같은값으로만 바꿔주면 된다.

노드개수만큼만 탐색하면 되니까 사실 훨씬 더 빠르다. 탐색도 여행경로의 노드중 아무거나 잡고 탐색 한번만 돌리면 된다.

여행경로가 성립되려면 해당 경로의 모든 노드의 부모는 같아야하기 때문이다.

 

 
int n, m, input;
vector<vector<int>> graph(201);
int routes[1001] = { 0 };
int parents[201] = { 0 };
int parentNode = 0;
bool visited[201] = { false };
 
 
void DFS(int node)
{
    for (int i = 0; i < graph[node].size(); ++i)
    {
        int nextNode = graph[node][i];
 
        if (visited[nextNode]) continue;
 
        visited[nextNode] = true;
        parents[nextNode] = parentNode;
        DFS(nextNode);
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> input;
 
            if (input == 1)
            {
                graph[i].push_back(j);
            }
        }
    }
 
    for (int i = 0; i < m; ++i)
    {
        cin >> routes[i]; 
    }
 
    parentNode = routes[0];
    parents[parentNode] = parentNode;
    visited[parentNode] = true;
    
    DFS(parentNode);
    
    for (int i = 1; i < m; ++i)
    {
        if (parents[routes[i]] != parentNode)
        {
            cout << "NO";
            return 0;
        }
    }
 
    cout << "YES";
}

 

플로이드와샬은 8ms, 유니온파인드는 0ms가 나왔다.