[BOJ]16947번: 서울 지하철 2호선 (c++)

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

16947번: 서울 지하철 2호선

 

 

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

using namespace std;

const int MAX = 3000;
int info[MAX + 1];

enum flag { NOT_CYCLE = -2, CYCLE_NOT_FOUND = -1, VISITED = 1, CYCLE = 2 };

/*
	깊이 우선 탐색으로 싸이클 찾기
	반환값 < 0 : 싸이클을 아직 못찾았거나, 싸이클 바깥의 노드일 때
	반환값 > 0 : 싸이클을 찾았고, 반환값은 해당 시점의 탐색 노드
*/
int dfs(vector<vector<int>> &graph, int now, int before)
{
	// 전에 방문했던 노드일때 --> 해당 노드 반환
	if (info[now] == VISITED)
	{
		return now;
	}

	// 방문 체크
	info[now] = VISITED;

	// 해당 노드와 연결되어 있는 노드 탐색
	for (int next : graph[now])
	{
		// 이전 노드로 다시 되돌아가지 않음
		if (next == before)
		{
			continue;
		}

		/*
			다음 노드, 현재 노드를 인수로 dfs 재귀함수 호출. 
			다음 노드의 상태 반환값 돌려받음.
		*/
		int res = dfs(graph, next, now);

		// 반환값 > 0 : 싸이클을 찾았고, 반환값은 해당 시점의 탐색 노드
		if (res >= 0)
		{
			info[now] = CYCLE;
			
			// 반환된 노드가 현재 노드와 일치하면, 이 이전의 노드는 이제 싸이클 바깥의 노드임
			return (res == now) ? NOT_CYCLE : res;
		}
		/*
			반환값이 NOT_CYCLE일 때
			: 이미 싸이클을 찾았고 해당 노드는 싸이클 영역 바깥의 노드라는 뜻. 
			불필요하게 반복문을 모두 돌릴 이유가 없어졌으므로 빠르게 종료.
		*/
		else if (res == NOT_CYCLE)
		{
			return NOT_CYCLE;
		}
	}
	return CYCLE_NOT_FOUND;
}

// 너비 우선 탐색으로 싸이클과 연결되어 있는 노드들의 거리 계산
void bfs(vector<vector<int>>& graph, vector<int> &cost)
{
	queue<int> q;
	for (int i = 1; i < graph.size(); ++i)
	{
		// 싸이클이면 --> 큐에 push
		if (info[i] == CYCLE)
		{
			q.push(i);
		}
		// 싸이클이 아니면 --> cost값을 음수로 설정 
		else
		{
			cost[i] = -1;
		}
	}
	
	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int next : graph[now])
		{
			// 싸이클이 아니고, 아직 방문하지 않은 노드일 때
			if (cost[next] < 0)
			{
				// 현재 노드의 cost값 + 1 하고 큐에 push
				cost[next] = cost[now] + 1;
				q.push(next);
			}
		}
	}
}

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

	// 입력
	int N;
	cin >> N;
	vector<vector<int>> graph(N + 1, vector<int>());
	for (int i = 0; i < N; ++i)
	{
		int first, second;
		cin >> first >> second;
		graph[first].push_back(second);
		graph[second].push_back(first);
	}

	// 깊이 우선 탐색으로 먼저 싸이클 찾기
	dfs(graph, 1, 0);

	// 너비 우선 탐색으로 각 노드들이 싸이클로부터 떨어진 거리 계산
	vector<int> cost(N + 1);
	bfs(graph, cost);

	// 출력
	for (int i = 1; i <= N; ++i)
	{
		cout << cost[i] << ' ';
	}

	return 0;
}

 

 

TIP1

먼저 문제를 보자. 

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

 

문제가 내포하고 있는 step은 2단계이다.

1. 순환선 - 싸이클을 찾아라 --> DFS

2. 각 역과 싸이클 사이의 거리를 구해라 --> BFS

따라서 이 문제는 DFS, BFS 순으로 모두 다 사용해야 함을 알 수 있다.

 

 

TIP2

정보가 너무 많으니,

enum으로 상수값 플래그들을 관리해주는 것이 적합하다.

enum flag { NOT_CYCLE = -2, CYCLE_NOT_FOUND = -1, VISITED = 1, CYCLE = 2 };

 

 

방문 여부, 싸이클 찾았나 여부, 싸이클 맞냐 여부 등등 플래그 값들이 너무 많았다.

이걸 각각 bool 배열로 만들어도 시간&공간 효율을 손해볼 것은 없다.

하지만 대신에 코드가 길어지는 단점이 있고, 논리적 결합성을 고려해주어야 하니까

열거형 타입을 사용합시다.