[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - 서울 지하철 2호선 (16947)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - 서울 지하철 2호선 (16947)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[그래프 1] - 서울 지하철 2호선 (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 ]

#include<iostream>
#include<algorithm>
#include<cstring> // memset 사용 위해
#include<queue>
using namespace std;
#define MAX 3001 // 값이 1부터 시작하므로, 즉 0을 사용하지 않으므로, 3001로 설정 (define은 ; 사용x)

/* 인접리스트 구현
	vector <int> a[n] : 사용자가 앞으로 입력하게 되는 갯수만큼 2차원 배열이 생성된다. (입력은 push_back 활용)
*/
vector <int> a[MAX]; // 간선
bool check[MAX]; // 방문여부

bool hasCycle; // Cycle을 가진다면 true로 변환 (디폴트값 false)
int pre[MAX]; // 이전에 방문했던 노드들
bool cycle[MAX]; // Cycle 노드 저장

int dist[MAX]; // 거리 저장

int N; // 역의 개수 (정점의 개수)



// bfs : 너비우선탐색
void bfs() { 
	
	queue<pair<int, int>> q;
	// pair<type, type> : 2개의 각각 지정한 타입을 저장하며, 저장한 값은 .first, .second로 각각 접근 가능)
	// 2개의 연관된 값에서, 각각의 조건에 따라 정렬한 결과를 얻고자 할 때 사용하면 좋다.

	for (int i = 1; i <= N; i++)
	{
		/* 사이클에 존재하는 노드라면? */
		if (cycle[i])
		{
			check[i] = true; // 사이클에 존재하는 노드들은, 이미 처리했다고 바꾸기
			q.push({ i,0 }); // 사이클에 존재하는 노드들은, 거리상 0의 값을 가짐
			// cf. dist[]의 경우에는, 0으로 디폴트값이 설정되어 있으므로, 따로 입력해줄 필요 x
		}
	}

	while (!q.empty())
	{
		// 사이클 내에 있는 한 지점으로부터, 연결된 간선에 대해 하나씩 거리 측정 시작
		int cur = q.front().first; // 해당 정점
		int dis = q.front().second; // 거리

		q.pop();

		check[cur] = true; 

		for (int i = 0; i < a[cur].size(); i++)
		{
			int next = a[cur][i]; // next = 현재 정점과 연결된 다음 정점
			if (check[next]) // 아직 거쳐오지 않았다면
			{
				continue;
			}

			dist[next] = dis + 1; // 다음 정점에, 거리 + 1 저장
			q.push({ next,dis + 1 }); // 큐에 넣기
		}
	}

}


// 사이클 찾기 함수
void findCycle(int cur) {
	check[cur] = true;
	
	for (int i = 0; i < a[cur].size(); i++)
	{
		/* 사이클을 찾았다면, 종료*/
		if (hasCycle) return;
		
		// 다음 방문 노드
		int next = a[cur][i];

		/* 방문한 적이 있으면 실행*/
		if (check[next]) 
		{
			// 부모가 아닌, 다른 방문했던 노드이면 사이클임.
			if (next != pre[cur])
			{
				cycle[cur] = true; // 사이클에 해당하는 노드들은, 모두 순환선에 포함됨. (따라서 순환선과의 거리는 0이 됨)
				hasCycle = true; // 사이클을 찾았다고 바꿔주기

				// cur의 부모노드가 결국, 사이클을 이루는 첫 노드가 될 때까지 while문 돌리기 
				while (cur != next)
				{
					cycle[pre[cur]] = true; // cur의 부모 노드가, 사이클(순환선)에 포함되어있다고 바꿔주기
					cur = pre[cur]; // cur의 부모노드로, cur를 바꿔주기
				}
				return;
			}
		}

		/* 방문한 적이 없으면 실행 */
		else
		{
			pre[next] = cur; // next 이전에 방문했던 노드는, cur이다.
			findCycle(next);
		}
	}

}


int main() {
	cin >> N;

	/* 역이 개수(정점의 개수) = 역과 역을 연결하는 구간의 정보 (간선의 개수) */
	for (int i = 0; i < N; i++) // 역과 역을 연결하는 구간의 정보 (간선의 정보)
	{
		int from, to;
		cin >> from >> to;

		a[from].push_back(to);
		a[to].push_back(from);
	}

	// Cycle이 존재하는지 찾기. (존재한다면, 그 해당 cycle[]을 true로 변환해주기)
	findCycle(1);

	// bfs에서 활용하기 위해, findCycle에서 사용했던 check를 fasle로 리셋해주기
	memset(check, false, 3001);

	// bfs 실행
	bfs();

	// 해당 정점과 순환선 사이의 거리 출력
	for (int i = 1; i <= N; i++)
	{
		cout << dist[i] << ' ';
	}

	return 0;
}

[ 코드 2 ]

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

#define MAX 3001

int N;
bool Cycle; // cycle을 가진다면 true로 변환
bool Visit[MAX]; // 방문여부
bool Check_Cycle_Station[MAX]; // 순환선은 하나가 아니라 여러개가 될 수도 있음. 따라서 사이클의 시작점인지를 기록하는 곳이 필요
vector <int> Station[MAX]; // 간선 정보 저장
vector <int> Answer; // 거리 정보 저장 

void Input() {
	cin >> N;

	// 간선의 정보 저장 (역과 역을 연결하는 구간의 정보)
	for (int i = 0; i < N; i++)
	{
		int a, b;
		cin >> a >> b;
		Station[a].push_back(b);
		Station[b].push_back(a);
	}
}

/* 순환선인지를 파악하기 위해 DFS함수를 사용 */
// DFS (현재 역, 시작 역, 경로의 수)
// 시작역을 고정시켜놓고 하기 때문에, 실제 함수를 호출할 때는 1-N번까지 모두 한번씩 시작역으로 설정하여 호출 필요 o)
void DFS(int cur, int start, int line) {

	/* 순환선을 찾았을 경우, 기록 후 반환 */
	// 현재역 = 시작역 && 최소 2개 이상의 경로를 지난 경우
	if (cur == start && line >= 2)
	{
		Cycle = true; // 순환선으로 체크
		return; // 반환
	}

	/* 순환선을 찾지 못함 */
	Visit[cur] = true; // 역 방문 표시

	for (int i = 0; i < Station[cur].size(); i++) // 현재 역과 연결된 모든 역을 탐색
	{
		int Next = Station[cur][i];
		
		if (Visit[Next] == false) // 아직 탐색하지 않은 역이라면
		{
			DFS(Next, start, line + 1); // 탐색 시작
		}
		else // 이미 탐색했던 역이라면
		{
			if (Next == start && line >= 2) // Next = start && 2개 이상의 경로를 지났을 때만
			{
				DFS(Next, start, line); // 다음 단계 호출
			}
		}
		
		/* 순환선을 찾았을 경우, 최종 반환 */
		if (Cycle == true) return;

	}
}

/* 가장 가까운 순환선과의 거리 확인 */
int BFS(int a) {
	memset(Visit, false, sizeof(Visit));

	queue<pair<int, int>> Q;
	Q.push(make_pair(a, 0)); 
	Visit[a] = true;

	while (!Q.empty())
	{
		int cur = Q.front().first; // 해당 역
		int cnt = Q.front().second; // a값과의 거리
		Q.pop();

		// 탐색 과정에서 순환선에 속해있는 역을 만나게 되면, 바로 거리를 반환시킴.
		if (Check_Cycle_Station[cur] == true)
		{
			return cnt;
		}

		for (int i = 0; i < Station[cur].size(); i++)
		{
			int Next = Station[cur][i];
			if (Visit[Next] == false)
			{
				Visit[Next] = true;
				Q.push(make_pair(Next, cnt + 1));
			}
		}
	}
}

/* BFS(순환값찾기) + DFS(순환선과의거리저장) + 출력 */
void Solution() {
	/* BFS */
	for (int i = 1; i <= N; i++)
	{
		memset(Visit, false, sizeof(Visit));
		Cycle = false;

		DFS(i, i, 0);

		if (Cycle == true)
		{
			Check_Cycle_Station[i] = true; // 사이클에 포함되어 있는 값이라고 표시
		}
	}

	/* DFS */
	for (int i = 1; i <= N; i++)
	{
		if (Check_Cycle_Station[i] == true) // 사이클에 포함되어 잇는 값일 경우
		{
			Answer.push_back(0); // 거리는 0
			continue; // 다음 진행
		}
		Answer.push_back(BFS(i));
	}

	/* 출력 */
	for (int i = 0; i < Answer.size(); i++)
	{
		cout << Answer[i] << " ";
	}
	cout << '\n';
}



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

	Input();
	Solution();

	return 0;
}