1976번

1976번 - 여행 가자

이 문제를 나는 처음에 연결요소의 갯수를 이용해서 문제를 풀었다.

도시들이 연결되어 있기만 한다면, 어떤 경로를 지나던 갈 수 있기 때문이다.

그리고 지금은 disjoint-set 을 배우고 있기 때문에 그 방식을 이용해서 풀어보았다.

하나의 트리 안에 있기 위해서는 각 도시들의 find 값, 즉 루트 노드가 같아야 한다는 점을 이용했다.

주의할 점

--> 나는 처음에 부모노드를 자기 자신으로 초기화 하는 것을 빼먹어서 처음에 문제를 틀림. 고칠 것

--> 처음에 나는 2중 for문에서 예를 들어 1은 0을 부모로, 0은 1을 부모로 해서 , 사이클이 생겨서 부모노드를 못찾는것이 아닌가

     혼자 고민했는데, merge 함수에서 이미 부모가 같을 때, 다를 때를 처리해주기 때문에 문제가 없었다.

<정답 코드 - disjoint-set>

#include<iostream>
#include<vector>
using namespace std;
 
int N, M;
vector<int> p;
 
int find(int x)
{
    if (x == p[x])
    {
        return x;
    }
 
    return p[x] = find(p[x]);
}
void merge(int x, int y)
{
    x = find(x);
    y = find(y);
 
    if (x != y)
    {
        p[y] = x;
    }
 
    return;
}
int main()
{;
    scanf("%d %d", &N, &M);
    p.resize(N);
 
    for (int i = 0; i < N; i++)
    {
        p[i] = i;
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int tmp;
            cin >> tmp;
            if (tmp == 1)
            {
                merge(i, j);
            }
        }
    }
 
    bool first = true;
    int parent;
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        if (first)
        {
            first = false;
            parent = find(tmp - 1);
        }
        else
        {
            if (parent != find(tmp - 1))
            {
                first = true;
                break;
            }
        }
        
    }
    
    if (!first)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}

<정답 코드 - 연결요소>

#include<iostream>
#include<vector>
using namespace std;
bool check[200];
int N, M;
vector<vector<int>> city;
void dfs(int s)
{
    check[s] = true;
 
    for (int i = 0; i < city[s].size(); i++)
    {
        int next = city[s][i];
 
        if (!check[next])
        {
            dfs(next);
        }
    }
}
int main()
{
    
    scanf("%d %d", &N, &M);
    city.resize(N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int tmp;
            cin >> tmp;
            if (tmp == 1)
            {
                city[i].push_back(j);
                city[j].push_back(i);
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < M; i++)
    {
        int tmp;
        cin >> tmp;
        if (!check[tmp-1])
        {
            ans++;
            dfs(tmp-1);
        }
    }
 
    if (ans == 1)
    {
        printf("YES\n");
    }
    else
    {
        printf("NO\n");
    }
 
    return 0;
}