[백준/BOJ] 16947번 서울 지하철 2호선 (C++)

www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

그래프 + DFS + BFS 유형의 복합적인 문제입니다. (다시 풀기)

먼저 순환선을 이루는 역을 알아내기 위해서 사이클을 만들어내는 정점을 찾아내야 하는데, DFS를 통해 탐색하다가 처음 시작 위치로 돌아오는 경우를 찾으면 됩니다. (16929번 문제와 비슷합니다.) 이러한 탐색을 1번 정점 ~ n번 정점까지 실행하면서 체크를 한 후, 사이클이 아닌 정점만 따로 BFS를 통해 사이클인 정점을 만나는 최소 거리를 구해주면 됩니다. 

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int n, start; 
vector<int> graph[3001];
bool cycle[3001], visit[3001], flag;

int BFS(int node) {
	queue<pair<int, int > > q;
	q.push( {node, 0} );
	visit[node] = true;
	
	while(!q.empty()) {
		int now = q.front().first;
		int dis = q.front().second;
		q.pop();
		if(cycle[now]) return dis;
			
		for(int i = 0; i < graph[now].size(); i++) {
			int next = graph[now][i];
			if(!visit[next]) {
				q.push( {next, dis + 1});
				visit[next] = true;
			}
		}
	}
}

void DFS(int now, int cnt) {
	for(int i = 0; i < graph[now].size(); i++) {
		int next = graph[now][i];
//		cout << "next : " << next << " cnt : " << cnt << "\n";
		if(cnt >= 2 && start == next) {
			flag = true;
			return;
		}
		if(visit[next]) continue;
		visit[next] = true;
		DFS(next, cnt + 1);
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for(int i = 0; i < n; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		graph[v1].push_back(v2);
		graph[v2].push_back(v1);
	}
	
	// 사이클 정점 찾기 (DFS) 
	for(int i = 1; i <= n; i++) {
		start = i;
		visit[start] = true;
		DFS(i, 0);
		if(flag) cycle[i] = true;
		flag = false;
		memset(visit, false, sizeof(visit));
	}
	
	// 사이클 정점까지의 최소 거리 찾기 (BFS) 
	for(int i = 1; i <= n; i++) {
		if(cycle[i]) cout <<"0 ";
		else {
			cout << BFS(i) << " ";
			memset(visit, false, sizeof(visit));
		}
	} 
}