알고리즘 공부
백준 경로찾기
컴퓨터과학
2023. 7. 16. 00:33
https://www.acmicpc.net/problem/11403
11403번: 경로 찾기
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
www.acmicpc.net
이거 문제가 좀 이해하기 힘들게 해놧네여 ..
문제 이해하는데 시간이 더 걸림;;
말그대로 그냥 0 경로에서 1,2,3,4,5 경로를 갈수 있으면
0 1 ,1,1,1,1 경로를 표기 해준다는 의미입니다. 하 문제 설명 너무 거지같네요
#include <iostream>
#include <vector>
#include <algorithm>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<bitset>
#include<cmath>
using namespace std;
void Prints(vector<vector<char>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << ",";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<bool>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << ",";
}
cout << endl;
}
cout << endl;
}
void Prints(vector<vector<int>>maps, int r, int c) {
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
cout << maps[i][j] << " ";
}
cout << endl;
}
//cout << endl;
}
struct Point {
int i;
int j;
int cnt = 0;
};
struct Data {
int index;
int cnt = 0;
int gc = 1;
};
int main() {
int n;
cin >> n;
vector<vector<int>>maps;
vector<vector<int>>answermaps;
vector<bool>tmpVisited(n, false);
vector<vector<bool>>bVisitied(n,tmpVisited);
vector<vector<bool>>initbVisitied(n, tmpVisited);
vector<bool>node(n, false);
for (int i = 0; i < n; i++) {
vector<int>tmpmaps;
for (int j = 0; j < n; j++) {
int tmp;
cin >> tmp;
tmpmaps.push_back(tmp);
if (tmp == 1) {
bVisitied[i][j] = true;
initbVisitied[i][j] = true;
}
}
maps.push_back(tmpmaps);
}
answermaps = maps;
for (int i = 0; i < n; i++) {
vector<int>saveNode;
bVisitied = initbVisitied;
for (int j = 0; j < n; j++) {
if (maps[i][j] == 1&&bVisitied[i][j]==true) {
queue<Point>q;
Point p;
p.i = i;//0
p.j = j;//3
q.push(p);
while (!q.empty()) {
Point start = q.front();
q.pop();
for (int t = 0; t < n; t++) {
//3 ,0 ...
if (maps[start.j][t] == 1 && bVisitied[start.j][t] == true) {
bVisitied[start.j][t] = false;
Point tmpP;
tmpP.i = start.j;
saveNode.push_back(t);
tmpP.j = t;
q.push(tmpP);
}
}
}
for (int y = 0; y < saveNode.size(); y++) {
answermaps[i][saveNode[y]]=1;
}
}
}
}
Prints(answermaps, n, n);
return 0;
}