https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
이 문제의 경우 전형적인 BFS 문제이다
자기와 연결되어 있는 루트를 BFS로 계속 따라가며 이어져있는 모든 점에 대해 표시만 해주면 되는 쉬운 문제다
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N;
int arr[100][100];
int ans[100][100];
void solution(int vertex) {
queue<pair<int, int>> bfsq;
for (int i = 0; i < N; i++) {
if (arr[vertex][i] == 1) {
bfsq.push({ vertex, i });
ans[vertex][i] = 1;
while (!bfsq.empty()) {
int start = bfsq.front().first;
int end = bfsq.front().second;
bfsq.pop();
for (int j = 0; j < N; j++) {
if (arr[end][j] == 1 &&ans[vertex][j]==0) {
bfsq.push({ end,j });
ans[vertex][j] = 1;
}
}
}
}
}
}
int main() {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
for (int i = 0; i < N; i++) {
solution(i);
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << ans[i][j]<<" ";
}
cout << endl;
}
}solution 함수를 설명을 하자면 solution 함수를 실행하면 매게변수로 vertex 즉 시작점이 넘어간다
그 후 arr를 참고하여 나와 연결되어있는 애들을 차례로 큐에 넣어준 후 차례로 pop시키며 그 애들과 연결된 애들을
계속 push한다 함과 동시에 ans배열에 값을 1로 바꿔준다.
예를들어 input으로
7
0 0 0 1 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
0 0 0 0 1 1 0
1 0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 1 0 0 0 0이렇게 들어 갔다고 치자 solution(1)을 실행시키면
현재 큐에 나와 연결되어 있는 0,4가 큐에 들어간다.
그후 0,4가 pop 되며 4와 연결되어 있는 4,5와 4,6이 들어간다
이와 동시에 ans[0][5]와 ans[0][6]의 값을 1로 바꿔준다.
그후 다시 4,5를 pop하면서
5,1을 큐에 넣어준다 그후 ans[0][1]을 1로 바꿔준다
그후 4,6을 pop한다
그후 6,7을 푸쉬하면서 ans[0][7]을 1로 바꿔준다
이러한 방식을 반복하면서 진행이된다.
그럼 이런식으로 해당 Vertex와 연결되어 있는 부분을 나타내주는 배열이 만들어진다
