[DFS, BFS] 백준 16947 - 서울 지하철 2호선

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번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.

예제 입력 1 

4
1 3
4 3
4 2
1 2

예제 출력 1 

0 0 0 0

예제 입력 2 

6
1 2
3 4
6 4
2 3
1 3
3 5

예제 출력 2 

0 0 0 1 1 2

 

---

문제를 어떻게 풀지 고민하느라 시간을 좀 썼다!

고민하다가 내린 결론은, dfs와 bfs를 모두 써야하는 문제로 보였다. 왜냐하면 dfs로 출발점까지 돌아오는 순환선을 발견할 수 있다. 깊이 우선 탐색이기 때문에, 너비 우선 탐색보다 더 빠르게 순환선을 찾을 수 있을 것이다.

순환선을 찾으면, bfs를 통해 그 순환선으로부터 떨어진 다른 점들에게 거리 + 1을 해주면 그 거리가 무조건 최소거리가 된다. 

 

• 순환선을 찾자!

모든 역을 출발점으로 두고 dfs를 호출했다.

lineVector 벡터 컨테이너에 출발점으로부터 깊이 탐색한 역들을 삽입해주었다. 

만약 dfs의 깊이가 1보다 크면서, 출발점으로 돌아왔다면 순환선이 될 것이다. 완성한 순환선은 circulationLine에 저장해주었다.

만약 순환선을 찾지 못했다면, lineVector를 비우고 다음 역을 출발점으로 바꿔 dfs를 다시 호출하도록 했다.

 

• 찾은 순환선은 어떻게 관리할까?

circulationLine 벡터 컨테이너에 저장했다. 그 후 circulationLine를 돌면서 bfs의 큐에 저장해주었다.

그런데 지금 생각해보니 순환선을 찾았을 당시에 큐에 저장하는게 메모리 측면에선 나았을 것 같다. 그래도 일단 좀 더 가독성 있는 코드 쪽으로 설명하겠다.

 

• 순환선으로부터의 모든 역의 거리 측정을 해야한다.

순환선들을 큐에 저장했다.

그 큐에서 요소들을 하나씩 pop()해주며, 그 역과 연결되어있는 역들은 순환선으로부터의 거리++를 해주면 된다. 그리고 그 값을 circleDistance 벡터 컨테이너에 저장해주었다.

그러면 무조건 최소거리로 저장될 것이다.

 

이후 circleDistance를 순회하며 저장된 값을 출력해주었다.

#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'
#define RED 1
#define BLUE 2

using namespace std;

vector<vector<int>> stations; // 입력된 역들
vector<int> visited; // 방문여부

int startStat; // 출발한 역
vector<int> circulationLine; // 찾은 순환선
vector<int> lineVector; // 저장하는 역

queue<int> bfsq;
vector<int> circleDistance; // 순환선으로부터의 거리

void clearVisit()
{
	for (int i = 0; i < visited.size(); ++i)
	{
		visited[i] = false;
	}
}
void dfs(int index, int depth) // 역, dfs깊이
{
	if (index == startStat && depth > 1) // 순환선 발견
	{
		circulationLine = lineVector;
		return;
	}

	visited[index] = true;
	for (int i = 0; i < stations[index].size(); ++i)
	{
		if (!visited[stations[index][i]]) // 아직 방문한 적 없는 역
		{
			lineVector.push_back(stations[index][i]);
			dfs(stations[index][i], depth + 1);
			lineVector.pop_back();
		}
		else
		{
			if (stations[index][i] == startStat && depth > 1) // 방문했다면, 순환선인지 확인하기
			{
				dfs(stations[index][i], depth);
			}
		}
	}
}
void bfs()
{
	while (!bfsq.empty())
	{
		int station = bfsq.front();
		bfsq.pop();

		for (int i = 0; i < stations[station].size(); ++i) // 순환선과 이어진 역들 보기
		{
			int nextStat = stations[station][i]; // 이어진 다음 역

			if (!visited[nextStat]) // 방문한적 없는 역
			{
				visited[nextStat] = true;
				circleDistance[nextStat] = circleDistance[station] + 1;
				bfsq.push(nextStat);
			}
		}
	}
}
int main()
{
	int N; // 노선의 수
	cin >> N;

	stations.assign(N + 1, vector<int>(0, 0));
	visited.assign(N + 1, 0);

	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		stations[a].push_back(b);
		stations[b].push_back(a);
	}

	for (int i = 1; i <= N; ++i)
	{
		if (circulationLine.empty()) // 순환선 못찾았을 때
			lineVector.clear();
		else
			continue;
		startStat = i;
		lineVector.push_back(i);
		dfs(i, 0); // 순환선 찾기
		clearVisit();
	}

	circleDistance.assign(N + 1, 0);
	for (int i = 0; i < circulationLine.size(); ++i) // 순환선 큐에 넣기
	{
		visited[circulationLine[i]] = true;
		bfsq.push(circulationLine[i]); // 순환선의 역들 큐에 넣기
	}

	bfs();

	for (int i = 1; i < circleDistance.size(); ++i) // 순환선 큐에 넣기
	{
		cout << circleDistance[i] << " ";
	}
}