baekjoon 11403:경로 찾기

baekjoon 11403 경로 찾기

11403번 경로 찾기

접근

각 node에서 dfs 돌리면 될거라고 생각했다. 그런데 이제 기본 dfs와 다르게 처음 자기가 시작하는 node에서는
visited라 표시하면 안되니까 좀 변형시켰다.

코드

#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<vector<int>>& v, vector<vector<bool>>& visited, int i, int x);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n; cin >> n;
  vector<vector<int>> v(n);
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      int temp;
      cin >> temp;
      v[i].push_back(temp);
    }
  }
  vector<vector<bool>> visited(n, vector<bool>(n, false));
  for(int i = 0; i < n; i++){
    dfs(v, visited, i, i);
  }
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      if(visited[i][j]) cout << "1 ";
      else cout << "0 ";
    }
    cout << "\n";
  }
  

  return 0;
}
void dfs(vector<vector<int>>& v, vector<vector<bool>>& visited, int i, int x){
  for(int j = 0; j < v.size(); j++){
    if(v[x][j] == 1 && !visited[i][j]){
      visited[i][j] = true;  //다음 node로 들어갈 때 visited true
      // cout << j << " ";
      dfs(v, visited, i, j);
    }
  }
}

배운 점

dfs의 변형을 또 배웠다. 그런데 이 문제 플로이드 와샬 알고리즘으로 풀 수 있다고 한다.
안그래도 플로이드 와샬은 all-pairs shortest-paths 니까 될꺼라고 생각했다.