[백준16947] 지하철 2호선 (C++)

📌 문제

BOJ 바로가기

한 개의 순환선과 여러 개의 지선으로 이루어진 그래프가 주어진다. 해당 위치의 인덱스가 순환선인 경우에는 0, 지선일 경우에는 순환선까지의 거리를 출력해야 한다. BFS와 DFS를 이용하여 해결할 수 있다.

🗡 풀이

📍 해당 역이 순환선인지 아닌지 판별하는 배열 circle을 선언하고, DFS를 이용해 배열의 내용을 채워주었다.
📍 해당 역이 순환선이고 연결된 노드가 3개 이상인 경우, 해당 인덱스를 큐에 push해주고 BFS를 실행해서 지선 역과 순환선 역 사이의 거리를 구했다. 이때 거리는 ans 배열에 담아두었다.

🥶 BFS를 돌리기 전 queue에 push하는 과정에서 visited 배열의 값을 true로 바꿔주는 걸 빼먹는 실수를 저질렀다. 이것 때문에 영문도 모르고 계속 틀렸다... 감사하게도 백준 질문게시판의 고수님이 반례를 찾아주셔서 정답을 제출할 수 있었다. 앞으로 그래프 탐색 문제를 풀 때는 visited배열의 값을 제때 잘 바꾸어 주었는지 꼼꼼히 체크해야겠다!

🚩 소스코드

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

vector<int> v[3001]; // 역 그래프 정보를 담은 배열
bool circle[3001] = { false }; // 순환선 여부를 알려주는 배열
int ans[3001] = { 0 }; // 순환선이 아닐 경우 거리를 담은 배열
bool visited[3001];

// DFS를 이용해 순환선일 경우 circle배열에 true를 채워줌
void dfs(int node, int start, int cnt)
{
	if (node == start && cnt >= 3)
	{
		circle[node] = true;
		return;
	}
	visited[node] = true;
	for (int i = 0; i < v[node].size(); i++)
	{
		if (visited[v[node][i]] == false || (v[node][i] == start && cnt >= 2))
			dfs(v[node][i], start, cnt + 1);
	}
}

// BFS를 이용해 지선일 경우 ans배열에 순환선까지의 거리를 채워줌
void bfs(queue<int> q)
{
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		for (int i = 0; i < v[node].size(); i++)
		{
			int next = v[node][i];
			if (!visited[next])
			{
				q.push(next);
				visited[next] = true;
				ans[next] = ans[node] + 1;
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	// 배열에 그래프 정보 담기
	for (int i = 1; i <= n; i++)
	{
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
	// DFS
	for (int i = 1; i <= n; i++)
	{
		memset(visited, false, sizeof(visited));
		int start = i;
		dfs(i, start, 0);
	}
	// BFS
	queue<int> q;
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= n; i++)
	{
		// 순환선과 지점의 연결점을 큐에 push!
		if (circle[i] == true && v[i].size() > 2)
		{
			q.push(i);
			visited[i] = true;
		}
	}
	bfs(q);
	// 결과 출력
	for (int i = 1; i <= n; i++)
	{
		if (circle[i] == true)
			cout << "0 ";
		else
			cout << ans[i] << ' ';
	}
}

다음 소스코드는 시간초과가 날 게 명백해 보여서 제출을 포기했던 코드이다.. 앞선 소스코드와는 반대로 지선에서 출발해서 순환선까지의 거리를 구한 다음 그 거리를 ans 배열에 넣었다. 하지만 이런 식으로 구하면 지선이 많은 노선의 경우 BFS가 계속해서 호출되기 때문에 연산이 굉장히 느리다. 그래서 아쉽지만 눈물을 머금고 코드를 갈아엎었다. 답은 잘 나온다😂

📍 수정 전 소스코드

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

int n;
vector<int> v[3001];
int circle[3001];
int ans[3001] = { 0 };
int memo[3001] = { 0 };
bool visited[3001];

void dfs(int node, int start, int cnt)
{
	if (node == start && cnt >= 3)
	{
		circle[node] = 0;
		return;
	}
	visited[node] = true;
	for (int i = 0; i < v[node].size(); i++)
	{
		if (visited[v[node][i]] == false || (v[node][i] == start && cnt >= 2))
			dfs(v[node][i], start, cnt + 1);
	}
}

void bfs(int node)
{
	queue<int> q;
	q.push(node);
	while (!q.empty())
	{
		if (circle[q.front()] == 0)
		{
			ans[node] = ans[q.front()];
			break;
		}
		int node = q.front();
		q.pop();
		for (int i = 0; i < v[node].size(); i++)
		{
			int next = v[node][i];
			if (!visited[next])
			{
				q.push(next);
				ans[next] = ans[node] + 1;
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
	memset(circle, -1, sizeof(circle));
	for (int i = 1; i <= n; i++)
	{
		memset(visited, false, sizeof(visited));
		int start = i;
		dfs(i, start, 0);
	}
	for (int i = 1; i <= n; i++)
	{
		if (circle[i] == 0)
			cout << circle[i] << ' ';
		else if (circle[i] != 0)
		{
			memset(visited, false, sizeof(visited));
			memset(ans, 0, sizeof(ans));
			bfs(i);
			cout << ans[i] << ' ';
		}
	}
}