백준 14412번 Ronald

문제 링크입니다: https://www.acmicpc.net/problem/14412

이 문제는 솔직히 말하자면 증명 없이 감으로 푼 문제입니다.

같은 학교 학우이신 Green55님(https://blog.naver.com/pasdfq/221367374753)은 백준 14927번 전구 끄기(http://jaimemin.tistory.com/699) 문제처럼 그리디하게 접근하셔서 푸셨습니다.

따라서 Green55님의 블로그에 작성된 코드를 참고하시는 것을 추천드립니다!!

저는 첫 번째 예제를 토대로 그래프를 계속 그려본 결과 그래프가 초기에 두개의 컴포넌트로 나뉘어있고 두 개의 컴포넌트들이 모두 완전 그래프라면 성립한다고 판단했습니다.

첫 번째 예제에서는 정점이 두개이고 간선이 0개입니다.

즉, 1 과 2 두개의 컴포넌트가 있고 각각은 하나의 정점이므로 완전그래프입니다.

(처음에는 간선이 0개이면 무조건 성립하는 줄 알았지만 N >= 3인 상태에서 간선이 0개이면 성립하지 않는 것을 알 수 있습니다.)

두 번째 예제에서는 정점이 4개이고 간선이 2개입니다.

1 과 3이 연결되어있고 하나의 컴포넌트는 이 둘로 이루어져있습니다.

마찬가지로, 2와 4가 연결되어있고 나머지 컴포넌트는 이 둘로 이루어져있습니다.

첫 번째 예제와 마찬가지로 모든 컴포넌트는 완전그래프입니다.

첫 번째 예제와 두 번째 예제처럼 직접 그려보면 제가 감으로 세운 조건이 성립해야지만 문제의 조건을 만족할 수 있다는 것을 알 수 있습니다.

하지만, 증명을 할 능력이 없기 때문에 저도 Green55님의 코드를 참고해서 그리디하게 접근하는 방법을 익혀야할 것 같습니다!

#include <iostream>

#include <vector>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N;

bool completeGraph;

vector<int> graph[MAX];

vector<int> v; //해당 컴포넌트 내 정점

bool edge[MAX][MAX];

bool visited[MAX];

 

void DFS(int city)

{

        v.push_back(city);

 

        for (int i = 0; i < graph[city].size(); i++)

        {

                 int next = graph[city][i];

                 if (!visited[next])

                 {

                         visited[next] = true;

                         DFS(next);

                 }

        }

}

 

//완전그래프인가?

void complete(void)

{

        for(int i=0; i<v.size(); i++)

                 for (int j = i + 1; j < v.size(); j++)

                         if (!edge[v[i]][v[j]])

                         {

                                 completeGraph = false;

                                 return;

                         }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int M;

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int city1, city2;

                 cin >> city1 >> city2;

 

                 graph[city1].push_back(city2);

                 graph[city2].push_back(city1);

                 edge[city1][city2] = true;

                 edge[city2][city1] = true;

        }

 

        int cnt = 0;

        completeGraph = true;

        for (int i = 1; i <= N; i++)

        {

                 if (cnt > 2 || !completeGraph)

                         break;

 

                 if (!visited[i])

                 {

                         v.clear();

                         visited[i] = true;

                         DFS(i);

                         complete();

                         cnt++;

                 }

        }

       

        //컴포넌트가 두개이고 두개 다 완전그래프일 경우

        if (cnt == 2 && completeGraph)

                 cout << "DA\n";

        else

                 cout << "NE\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~