백준 11774번 MOLEKULE

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

정점들이 양방향으로 이어진 트리가 주어졌을 때, 최장경로가 제일 작아지도록 단방향 그래프로 변형시키는 문제였습니다.

우선, 이 문제는 같은 학교 학우이신 Green55(구 ssangba55)님의 설명을 듣고 풀 수 있었던 문제였습니다.

Green55님의 해설(https://blog.naver.com/pasdfq/221358553139)입니다.

제 코드는 COCI 2015/2016 Archive에 있는 코드를 참고하여 작성했습니다.(아직 많이 부족하네요 ㅠ)

알고리즘은 아래와 같습니다.

1. 우선, 주어진 간선을 토대로 양방향 그래프로 입력받습니다.

2. 해당 정점을 시작으로 하는 단방향 간선이 있는지 여부를 connected 배열을 통해 표시합니다.

->0: 없다, 1: 있다

3. 트리는 사이클을 형성하지 않기 때문에 어느 정점을 기준으로 해도 상관 없습니다.

-> 편의상 1번 정점이 루트라고 하겠습니다.

4. 1번 정점에서부터 시작하는 단방향 간선은 없다고 가정합니다.(connected[1] = 0)

5. 이후에는 DFS(Depth First Search)를 하는데 BFS처럼 큐에다가 정점을 넣어가며 connected 배열을 표시합니다.

i) 현재 정점을 시작으로 하는 단방향 간선이 있다면 현재 정점과 연결되어있는 정점을 시작으로 하는 단방향 간선은 없습니다.

ii) 반대로 현재 정점을 시작으로 하는 단방향 간선이 없다면 현재 정점과 연결되어있는 정점을 시작으로 하는 단방향 간선은 있습니다.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

 

const int MAX = 100000 + 1;

 

int N;

int a[MAX], b[MAX];

int connected[MAX]; //연결되었는지 여부

vector<int> graph[MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N;

 

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

        {

                 cin >> a[i] >> b[i];

 

                 graph[a[i]].push_back(b[i]);

                 graph[b[i]].push_back(a[i]);

        }

 

        memset(connected, -1, sizeof(connected));

        connected[1] = 0; // 1번 정점을 시작으로 하는 단방향 간선이 없다고 가정

 

        queue<int> q;

        //트리이므로 1번 정점을 루트로 가정

        q.push(1);

 

        while (!q.empty())

        {

                 int curVertex = q.front();

                 q.pop();

 

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

                 {

                         int vertex = graph[curVertex][i];

                         //이미 확인한 정점

                         if (connected[vertex] != -1)

                                 continue;

 

                         connected[vertex] = 1 - connected[curVertex];

                         q.push(vertex);

                 }

        }

 

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

                 cout << connected[a[i]] << "\n";

 

        return 0;

}

 

개발환경:Visual Studio 2017

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