일반적인 DFS문제다. 하지만 방향성이 있는 그래프라는 것을 간과하고… 엄청난 삽질을 했다….. 나와같은 피해자가 나오지 않기를….ㅠ_ㅠ
메인에서 1~N까지 DFS를 돌려서 방문하지 않은 곳이면 체크해나가면 된다. DFS마다 target을 넘겨도 되고, 전역변수 visited를 만들어서 메인에서 visited의 값을 변경해줬다.
참 쉽게 풀 수 있는 문제인데 문제를 잘못 읽거나 잘못된 생각의 오류에 빠지면 끝도 없이 나락으로 빠져드는 것 같다…
풀이보기
```c++
#include <iostream>
#include <vector>
using namespace std;
int map[101][101];
bool connected[101][101];
int visited;
vector<vector <int>> graph;
int N;
void dfs(int n) {
for(int i=0; i<graph[n].size(); i++) {
int next = graph[n][i];
if(!connected[visited][next]) {
connected[visited][next] = true;
dfs(next);
}
}
}
int main(int argc, const char * argv[]) {
scanf("%d", &N);
graph.resize(N+1);
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
scanf(" %d", &map[i][j]);
if(map[i][j]) graph[i].push_back(j);
}
}
for(int i=1; i<=N; i++) {
visited = i;
dfs(i);
}
// printf("===================\n");
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
printf("%d ", connected[i][j]);
}
printf("\n");
}
return 0;
}
```