https://www.acmicpc.net/problem/11403
문제
> 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
> 첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다.
> 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다.
> i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다.
> i번째 줄의 i번째 숫자는 항상 0이다.접근
입력으로 주어진 행렬은 쉽게 생각해 인덱스가 1부터 시작해서 각각 1이 있는 좌표는 행, 열이 그래프의 경로 행점에서 열 점까지 간선이이어져 있다는 뜻이다.
즉, 예제 1로 보면 1,2 2,3 3,1에 1이 있으므로 이 말은
점1과 점2가 연결되어있고 점2와 점3이 연결되어있고 점3과 점1이 연결되어있다는 뜻이다.
이걸 관계도를 그려보면 세 점은 순환을 이루고 있는구조가 된다.
따라서 점1은 점2로, 점2를 지나 점3으로, 점2와3을 지나 다시 점 1로 올 수 있고,
점2는 점3으로, 점3을지나 점1로 점3과1을 지나 다시 점2로 오며
점3은 점1로, 점1을 지나 점2로 점1과2를 지나다시 점3으로올 수 있다.
정리하면 점 1은 1,2,3 다 갈 수 있고, 2도 1,2,3 다 가며, 3도 1,2,3 다 갈 수 있다.
그래서 출력 결과가 1,1,1,1,1,1,1,1,1형태로 나오는거다.
그래서 그래프 탐색을 이용해 문제에서 주어진 경로를 배열에 저장해 놓고, 이를 기반으로 점 1부터 N까지 전부 돌며 갈 수 있는 점을 마킹하면 된다.
문제해결
> 입력으로 주어진 배열을 이중 반복문으로 입력을 받으며 1이면 해당 i와 j를 이용해 점 사이 간선의 관계를 저장하는 node벡터에 저장한다.
> 저장이 끝나면 1부터 점 개수만큼 Graph 메소드에 넣어 돌린다. 그럼 여기서 각 점이 갈 수 있는 점에 대한 마킹이 되어 결과 배열이 생성된다.
> 이 결과를 출력한다.
> Graph메소드에선 그래프 탐색과 흐름은 비슷하지만
함수 안에서 방문 처리 벡터를 선언해주면서 각 점이 이미 왔던 점인지 체크한다.
> 밑에 다음 탐색 대상 처리부에서 다음 탐색 대상이 존재해 스택에 넘겨지면 현 점에서 그 점을 갈 수 있다 이므로 이를 결과 벡터인 rst에 (현점)(갈점)으로 인덱스를 잡아 마킹한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
int N;
vector<vector<int>> node;
vector<vector<bool>> rst;
void Graph(int start)
{
stack<int> s;
s.push(start);
vector<bool> visited(N+1, false);
while (!s.empty())
{
int t = s.top();
s.pop();
if (visited[t]) continue;
visited[t] = true;
for (auto a : node[t])
{
s.push(a);
rst[start][a] = true;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
node.resize(N + 1, vector<int>());
rst.assign(N + 1, vector<bool>(N + 1, false));
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
int tmp;
cin >> tmp;
if (tmp == 1) node[i].push_back(j);
}
}
for (int i = 1; i <= N; i++) Graph(i);
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cout << (rst[i][j] ? 1 : 0) << " ";
}
cout << '\n';
}
}
후기
문제 행렬이해가 젤 어려웠다. 이해 하고 난뒤는 그래프 탐색 부 처리가 복잡했지만 방문처리, 결과 저장을 하나로 안하고 따로 처리하니 잘 되었다.
