[c++] 백준 : 11430번 경로찾기

DFS로 계속 탐색해주면서 array의 값을 바꾸어 주었다.
계속 풀었는데 시간초과가 나서 미쳐버리는 줄 알았다..계속 보완한다고 보완해서 아래코드까지 작성했는데 출력결과는 잘 나오는데 시간초과가 나서 어쩔 수 없이..지피티의 힘을 조금 빌렸다..

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > array1; // 동적 2차원 벡터
vector<bool> visited;      // 동적 방문 배열
vector<vector<int> > v;
int N; 

void def(int i, int i2){
  visited[i] = true;
  for(int k = 0;k<v[i].size();k++){
    int a = v[i][k];
    array1[i2][a] = 1;
    if(visited[a] == false){
          def(a, i2);
    }
  }
  visited[i] = false;
}


int main(void){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin>>N;
  array1.resize(N,vector<int>(N,0));
  visited.resize(N,false);
  v.resize(N);

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      int a;
      cin>>a;
      if(a == 1){
        v[i].push_back(j);
      }
    }
  }

  for(int i=0;i<N;i++){
      def(i, i);
  }

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cout<<array1[i][j]<<" ";
    }
    cout<<'\n';
  }
}

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > array1; // 동적 2차원 벡터
vector<bool> visited;      // 동적 방문 배열
vector<vector<int> > v;
int N; 

void def(int i, int i2){
  visited[i] = true;
  for(int k = 0;k<v[i].size();k++){
    int a = v[i][k];
    //추가한 부분
    if(array1[i2][a] == 0){
      array1[i2][a] = 1;
    if(visited[a] == false){
          def(a, i2);
    }
    }
    
  }
  visited[i] = false;
}


int main(void){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  cin>>N;
  array1.resize(N,vector<int>(N,0));
  visited.resize(N,false);
  v.resize(N);

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      int a;
      cin>>a;
      if(a == 1){
        v[i].push_back(j);
      }
    }
  }

  for(int i=0;i<N;i++){
      def(i, i);
  }

  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cout<<array1[i][j]<<" ";
    }
    cout<<'\n';
  }
}

array의 값이 1인지 0인지 판단하여서 0이면 깊이탐색을 해주니 시간초과가 해결되었다..이거 생각은 했었는데 1시간 넘게 계속 풀고 있으니까 생각이 좀 꼬였었던것같다. 다음부터는 어떻게 풀지 미리 구상을 하고 코드를 작성해야겠다.