백준 16947번 서울 지하철 2호선

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

16947번: 서울 지하철 2호선

 

 

<접근방법>

싸이클을 어떻게 찾을지가 관건인 문제입니다.

bfs로는 불가능합니다. <- 시뮬레이션 돌려보면 바로 알 수 있습니다.

 

dfs로 찾아야하는데 방문처리와 정점이 최소 3개여야 싸이클이 형성되는 것을 생각해야합니다.

그 후에는 bfs로 거리계산을 쉽게 할 수 있습니다.

 

---

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

struct info {
	int now, t;
};

int n;
bool visit[3000];
bool cycle[3000];
bool found;

vector<int> dist[3000];

void dfs(int start, int cur, int cnt) {
	if (start == cur && cnt >= 2) {
		cycle[cur] = true;
		return;
	}
	visit[cur] = true;
	for (int i = 0; i < dist[cur].size(); i++) {
		int next = dist[cur][i];

		if (!visit[next]) dfs(start, next, cnt + 1);
		else if (start == next && cnt >= 2) dfs(start, next, cnt);

		if (found) return;
	}
}

int bfs(int start) {
	queue <info> q;
	bool visit[3000] = { false, };

	q.push({ start, 0 });
	visit[start] = true;

	while (!q.empty()) {
		info t = q.front();
		q.pop();
		int now = t.now;
		int time = t.t;

		if (cycle[now]) {
			return time;
		}

		for (int i = 0; i < dist[now].size(); i++) {
			int next = dist[now][i];

			if (visit[next]) continue;

			q.push({ next, time + 1 });
			visit[next] = true;
		}
	}
}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;

		cin >> a >> b;
		a--; b--;
		dist[a].push_back(b);
		dist[b].push_back(a);
	}

	for (int i = 0; i < n; i++) {
		memset(visit, false, sizeof(visit));
		dfs(i, i, 0);
	}

	for (int i = 0; i < n; i++) {
		if (cycle[i]) {
			cout << 0 << ' ';
			continue;
		}
		cout << bfs(i) << ' ';
	}
	puts("");

	return 0;
}

 

 

---

 

 

<느낀 점>

-알고리즘 구현 전에 검증을 해보자