[ BOJ / C++ ] 17352번 : 여러분의 다리가 되어 드리겠습니다!

[ BOJ ] 17352번 : 여러분의 다리가 되어 드리겠습니다!

문제 : https://www.acmicpc.net/problem/17352

---

[  문제  ]

선린월드에는 N개의 섬이 있다. 섬에는 1, 2, ..., N의 번호가 하나씩 붙어 있다. 

그 섬들을 N - 1개의 다리가 잇고 있으며, 어떤 두 섬 사이든 다리로 왕복할 수 있다.

어제까지는 그랬다.

 

"왜 다리가 N - 1개밖에 없냐, 통행하기 불편하다"며 선린월드에 불만을 갖던 욱제가 다리 하나를 무너뜨렸다!

안 그래도 불편한 통행이 더 불편해졌다. 서로 왕복할 수 없는 섬들이 생겼기 때문이다.

일단 급한 대로 정부는 선린월드의 건축가를 고용해, 서로 다른 두 섬을 다리로 이어서 다시 어떤 두 섬 사이든 왕복할 수 있게 하라는 지시를 내렸다.

 

그런데 그 건축가가 당신이다! 안 그래도 천하제일 코딩대회에 참가하느라 바쁜데...

[  입력  ]

첫 줄에 정수 N이 주어진다. (2 ≤ N ≤ 300,000)

그 다음 N - 2개의 줄에는 욱제가 무너뜨리지 않은 다리들이 잇는 두 섬의 번호가 주어진다.

[  출력  ]

다리로 이을 두 섬의 번호를 출력한다. 여러 가지 방법이 있을 경우 그 중 아무거나 한 방법만 출력한다.

---

[  문제 접근 및 풀이  ]

문제에서는 트리 구조를 가지고 있는 섬들을 잇고 있는 N-1개의 다리에서

1개를 부숴 2개의 트리로 나뉘게 되었다.

따라서 트리 1개를 돌면서 이어져 있지 않은 섬 하나와 1번 섬을 잇게 된다면

또다른 트리 구조를 가지고 있는 섬들이 1번 섬의 서브 트리가 되므로

다시 어떤 두 섬 사이를 왕복할 수 있게 된다.

 

1번 섬을 큐에 넣은 후 1번과 이어져있는 모든 섬들을 방문 처리 이후

이어져있지 않은 섬과 1번 섬을 출력 후 종료 하였다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int N,v,u,vis[300001];
vector<int> V[300001];
queue<int> q;
void Q_17352();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_17352();
}
void Q_17352(){
    cin >> N;
    for(int i=0;i<N-2;i++){
        cin >> v >> u;
        V[v].push_back(u);
        V[u].push_back(v);
    }
    q.push(1);
    vis[1]=true;
    while(!q.empty()){
        auto cur=q.front(); q.pop();
        for(auto x:V[cur]){
            if(vis[x]) continue;
            q.push(x);
            vis[x]=true;
        }
    }
    for(int i=1;i<=N;i++){
        if(!vis[i]){cout << "1 "<< i; return;}
    }
}

---