백준 16947 서울 지하철 2호선 c++

https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

---

문제

서울 지하철 2호선은 다음과 같이 생겼다.

지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.

두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.

지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.

입력

첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.

출력

총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

---

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

int N;
int map[3001];
bool visit[3001];
vector<int> rel[3001];
bool cycle[3001];//사이클의 일원인지 판별
int first;
int pre[3001];//이전역을 담을 배열
vector<int> result(3001, 999);//일부로 높은 값 999로 초기화

int bfs(int start,int cnt)
{
	visit[start] = true;
	for (int i = 0; i < rel[start].size(); i++)
	{
		if (visit[rel[start][i]])//다음 정점을 방문햇다면 패스
			continue;
		else//방문 안했을 때
		{
			if (cycle[rel[start][i]] == true)//다음 정점이 순회노선이라면
			{
				cnt++;
				result[first] = min(result[first], cnt);//기존에 있었던 값과 비교하여 작은(순회노선에 가까운 값)으로
			}
			else//다음 정점이 순회 노선이 아니라면
			{
				bfs(rel[start][i], cnt + 1);
			}
		}
	}
	return result[first];
}

void dfs(int start)
{
	visit[start] = true;
	for (int i = 0; i < rel[start].size(); i++)
	{
		int next = rel[start][i];
		if (visit[next] == false)
		{
			pre[next] = start;
			dfs(next);
		}
		if (visit[next] == true)//다음 역이 방문한 역일 때
		{
			if (next == first&&next!=pre[start])//다음역이 시작역이고, 이번역의 전역이 아닐 때
			{
				cycle[start] = true;//지금까지 지나친 역들을 cycle이라 본다.
				while (start != next)
				{
					cycle[pre[start]] = true;
					start = pre[start];
				}
				return;
			}
		}
	}
	return;
}

int main()
{
	cin >> N;
    //입력받고 역 연결
	for (int i = 1; i <= N; i++)
	{
		int a, b;
		cin >> a >> b;
		rel[a].push_back(b);
		rel[b].push_back(a);
	}
    //시작역(first)을 미리 정하고 dfs함수 실행 끝나면 초기화
	for (int i = 1; i <= N; i++)
	{
		first = i;
		dfs(i);
		memset(visit, false, 3001);
	}
	for (int i = 1; i <= N; i++)
	{
		if (cycle[i])//사이클 역이라면 0
		{
			result[i] = 0;
			continue;
		}
		else
		{
			int count = 0;
			first = i;
			result[i] = bfs(i,count);
			memset(visit, false, 3001);
		}
	}
	for (int i = 1; i <= N; i++)
	{
		cout << result[i] << ' ';
	}
}