서울 지하철 2호선은 다음과 같이 생겼다.
지하철 2호선에는 51개의 역이 있고, 역과 역 사이를 연결하는 구간이 51개 있다. 즉, 정점이 51개이고, 양방향 간선이 51개인 그래프로 나타낼 수 있다. 2호선은 순환선 1개와 2개의 지선으로 이루어져 있다. 한 역에서 출발해서 계속 가면 다시 출발한 역으로 돌아올 수 있는 노선을 순환선이라고 한다. 지선은 순환선에 속하는 한 역에서 시작하는 트리 형태의 노선이다.
두 역(정점) 사이의 거리는 지나야 하는 구간(간선)의 개수이다. 역 A와 순환선 사이의 거리는 A와 순환선에 속하는 역 사이의 거리 중 최솟값이다.
지하철 2호선과 같은 형태의 노선도가 주어졌을 때, 각 역과 순환선 사이의 거리를 구해보자.
입력
첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호가 매겨져 있다. 임의의 두 역 사이에 경로가 항상 존재하는 노선만 입력으로 주어진다.
출력
총 N개의 정수를 출력한다. 1번 역과 순환선 사이의 거리, 2번 역과 순환선 사이의 거리, ..., N번 역과 순환선 사이의 거리를 공백으로 구분해 출력한다.
#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include <map>
using namespace std;
int n;
bool circle = false;
int circlestart;
void findcircle(vector<vector<int>>&v,int idx, int elem,int *check) {
int s = v[idx][elem];
if (s == check[idx]) { return; }
if (check[s] > 0 || check[s]==-1) { circlestart = s; check[s] = idx; circle = true; return; }
check[s] = idx;
idx = s;
for (int i = 0; i < v[idx].size(); i++) {
findcircle(v, idx, i, check);
if (circle == true) { break; }
}
return;
}
int finddiff(vector<vector<int>>&v, map<int,bool>&m,int yuk) {
int count = 0;
int check[3002];
memset(check, 0, sizeof(check));
queue<int>q;
q.push(yuk);
while (!q.empty()) {
int search = q.front();
q.pop();
if (m[search] == true) { return check[search]; }
for (int i = 0; i < v[search].size(); i++){
if (check[v[search][i]] == 0) {
check[v[search][i]] = check[search]+1;
q.push(v[search][i]);
}
}
}
return count;
}
int main() {
cin >> n;
vector<vector<int> > v(n+1);
vector<int> route;
map<int, bool> m;
int check[3002]; //3000까지고 3000을 참조하려면 적어도 3001 까지는 있어야한다.
memset(check, 0, sizeof(check));
for (int i = 1; i <= n; i++) {
int yuk1;
int yuk2;
cin >> yuk1;
cin >> yuk2;
v[yuk1].push_back(yuk2);
v[yuk2].push_back(yuk1);
}
for (int i = 1; i <= n; i++) { //모든 노드에 대해서 탐색을 해야함 하지 않으면 틀린다고 나온다
memset(check, 0, sizeof(check));
check[i] = -1;
circlestart = i;
findcircle(v, i, 0, check);
if (circle == true) {
int idx = circlestart;
while (1) {
if (m[idx] == false) {
m[idx] = true;
idx = check[idx];}
else { break; }
}
break;
}
circle = false;
}
for (int i = 1; i <= n; i++) {
int res = finddiff(v,m,i);
cout << res << " ";
}
cout << endl;
return 0;
}어떤 알고리즘 어떤 논리로 그 알고리즘을 썼는지 ?
- 간선리스트를 사용해서 인접한 노드의 관계를 정의했다.
- BFS, DFS 모두 사용하였다. dfs의 경우 순환역을 추적하기 위해서는 dfs를 사용했는데 깊이 탐색이 더 빠를 것 같다는 생각과 BFS는 주로 최솟값을 구하기 위해 사용 되기 때문에 dfs 탐색을 선택했다. 특정역의 순환역으로부터의 거리는 가장 짧은 거리를 구하는 것이므로 bfs 를 썼다.
헷갈렸던점
- 헷갈렸던 것은 어떤 노드를 시작으로 탐색을 해야하는데 시작 노드를 1일때 부터 n일 때까지 모두 탐색해 봐야하는지 궁금 했다. 시작노드 1로만 해서 순환 영역 탐색할 때 테케는 다 통과 됐지만 제출을 하면 틀렸다고 나온다. 어떤 반례가 있는것 같은데 아직 그걸 찾지 못했다.
- 순환영역이 여러개일 수도 있는지 궁금했다. 문제의 의도는 순환영역이 1개일 때만 생각을 하는 것 같았다. 여러개가 아닐 이유가 뭔지에 대해서도 생각해 봐야 할 것 같다.
- 막상 bfs dfs 동시 구현해야하니까 좀 머리가 아팠다.
