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

문제

서울 지하철 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 <vector>
#include <queue>

using namespace std;

int N;
int visited[3001];
int dist[3001];
vector<int> edge[3001];

int dfs(int curr, int prev)
{
	int i;
	int res;
	int next;

	if (visited[curr])
		return curr;
	visited[curr] = 1;
	for (i = 0; i < edge[curr].size(); i++)
	{
		next = edge[curr][i];
		if (next == prev)
			continue;
		res = dfs(next, curr);
		if (res == -2)
			return -2;
		if (res > 0)
		{
			visited[curr] = 2;
			if (res == curr)
				return -2;
			return res;
		}
	}
	return -1;
}

void bfs()
{
	queue<int> q;
	int i;
	int curr;
	int next;

	for (i = 1; i <= N; i++)
	{
		if (visited[i] == 2)
			q.push(i);
	}
	while (!q.empty())
	{
		curr = q.front();
		q.pop();
		for(i = 0; i < edge[curr].size(); i++)
		{
			next = edge[curr][i];
			if (visited[next] == 2)
				continue;
			visited[curr] = 2;
			dist[next] = dist[curr] + 1;
			q.push(next);
		}
	}
}

int main()
{
	int i;
	int a;
	int b;
	int answer = 1;

	cin >> N;
	if (N < 3 || N > 3000)
	{
		return -1;
	}
	for (i = 0; i < N; i++)
	{
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs(1, 0);
	bfs();
	for (i = 1; i <= N; i++)
	{
		cout << dist[i] << " ";
	}
	cout << endl;

	return 0;
}

 

1. DFS로 사이클 찾기

이 함수의 return 값은 다음과 같다.

• -2 : 이미 찾은 사이클의 시작 노드
• -1 : 사이클에 속하지 않음
• 1 ~ N : 노드가 속하는 사이클의 시작 노드

 

첫번째 노드인 1부터 시작한다.

1. 현재 노드가 이미 방문된 노드라면 이 노드의 번호를 return 한다.
2. 현재 노드가 방문되지 않은 노드라면 visited에 방문을 기록한다. 
3. 현재 노드와 연결된 모든 노드를 확인한다.
4. 연결된 노드가 이전 노드와 동일하면 되돌아가지 않기 위해 넘긴다.
5. 연결된 노드를 기준으로 탐색한다.
6. 연결된 노드가 이미 찾은 사이클의 시작 노드이면 -2를 return 한다.
7. 연결된 노드가 사이클에 속하면 visited에 표시한다.
8. 현재 노드가 시작 노드라면 -2를 return 한다.
9. 사이클에 속하지 않으면 -1을 return 한다.

 

2. BFS로 거리 구하기

사이클에 속한 노드들을 기준으로 모든 노트를 탐색한다.

현재 노드에 연결된 모든 노드를 확인하여 사이클에 속하지 않는 노드들의 거리를 계산한다.

 

링크

16947번: 서울 지하철 2호선

inbdni/Baekjoon