BOJ 11097, 도시 계획
ProblemSolving ·이 문제는 SCC문제입니다. 한동안 SCC 알고리즘에 허덕이다가 오늘 제대로 된 SCC 문제 하나 푼 것 같아서 포스팅하기로 했습니다.
이 문제는 SCC와 플로이드 워셜 알고리즘을 합친 문제입니다! SCC도 어렵고 플로이드 워셜도 안풀어본지 오래되서 정말 끙끙 앓았습니다. 저처럼 힘겨울 분들을 위해서 코드를 가져왔습니다.
SCC는 코사라주 알고리즘을 사용하였습니다.
이 문제는 착각할 수 있는 포인트가 간선을 지운다는 느낌이 있는데 간선을 새로 설정해준다고 생각하시는게 편할 것 같습니다!!! 갈 수 있는 도로망을 설정해준다?는 느낌!
풀이
첫 번째, 주어진 간선을 이용해서 코사라주 알고리즘을 이용해서 SCC로 묶어준다!
두 번째, 묶어준 SCC그룹안에서 최소한의 도로망을 설정해준다! 또 arr배열에 노드가 몇번째 SCC로 묶여있는지 체크!
세 번째, ans 배열에 SCC그룹들의 간선을 체크해준다!
네 번째, ans 배열을 3중 포문을 이용하여 플로이드 워셜로 불필요한 간선을 제거해준다!
다섯 번쨰, 마지막으로 SCC그룹 끼리 갈 수 있다면 어느 노드(도시)끼리 연결지어도 상관없기때문에 SCC그룹의 맨앞에 있는 도시들을 연결시켜준다.
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<functional>
#include<stack>
using namespace std;
vector<vector<int>> v; // 정방향
vector<vector<int>> rv; // 역방향
vector<vector<int>> scc;
vector<int> newscc;
vector<pair<int, int>> bs; // 정답 간선
stack <int> s;
int V, K, t;
int chk[303], chk2[303];
int output[303][303]; // 전체 노드 간선
int ans[303][303]; // scc 간선
int arr[303]; // scc 번호
void dfs(int now)
{
chk[now] = 1;
for (int i = 0; i < v[now].size(); i++)
{
int next = v[now][i];
if (chk[next] == 0)
dfs(next);
}
s.push(now);
}
void dfs2(int now)
{
chk2[now] = 1;
newscc.push_back(now);
for (int i = 0; i < rv[now].size(); i++)
{
int next = rv[now][i];
if (chk2[next] == 0)
dfs2(next);
}
}
int main()
{
scanf("%d", &t);
while (t--)
{
scanf("%d", &V);
memset(chk, 0, sizeof(chk));
memset(chk2, 0, sizeof(chk2));
memset(arr, 0, sizeof(arr));
memset(ans, 0, sizeof(ans));
memset(output, 0, sizeof(output));
K = 0;
bs.clear();
scc.clear();
v.clear();
rv.clear();
v.resize(V + 1);
rv.resize(V + 1);
for (int i = 1; i <= V; i++)
for(int j = 1; j <= V; j++)
{
char a;
scanf(" %1c", &a);
if (i == j)
continue;
if (a == '1')
{
output[i][j] = 1;
v[i].push_back(j);
rv[j].push_back(i);
}
}
for (int i = 1; i <= V; i++)
if (chk[i] == 0)
dfs(i);
while (!s.empty())
{
int now = s.top();
s.pop();
if (chk2[now] == 1)
continue;
newscc.clear();
dfs2(now);
scc.push_back(newscc);
for (int i = 0; i < newscc.size(); i++) // 최소한의 도로망 설정
{
arr[newscc[i]] = scc.size();
if (newscc.size() == 1) // scc그룹에 노드가 1개면 간선 불필요!
continue;
if (i == newscc.size() - 1)
bs.push_back({ newscc[i], newscc[0] });
else
bs.push_back({ newscc[i], newscc[i + 1] });
K++; // 도로망 개수 체크
}
}
for(int i = 1; i <= V; i++) // scc 간선 체크
for (int j = 1; j <= V; j++)
{
if (arr[i] == arr[j]) continue;
if (output[i][j] == 1)
ans[arr[i]][arr[j]] = 1;
}
for(int k = 1; k <= scc.size(); k++) // scc 불필요 간선 삭제
for (int i = 1; i <= scc.size(); i++)
for (int j = 1; j <= scc.size(); j++)
{
if (i == k || k == j || i == j) continue;
if (ans[i][j] && (ans[i][k] && ans[k][j]))
ans[i][j] = 0;
}
for (int i = 1; i <= scc.size(); i++)
for (int j = 1; j <= scc.size(); j++)
{
if (i == j) continue;
if (ans[i][j] == 1)
{
bs.push_back({ scc[i - 1][0], scc[j - 1][0] });
K++;
}
}
printf("%d\n", K);
for (int i = 0; i < bs.size(); i++)
printf("%d %d\n", bs[i].first, bs[i].second);
printf("\n");
}
return 0;
}