백준_경로찾기

https://www.acmicpc.net/problem/11403

[ 나의 해결법 ]

노드 1을 시작점으로 깊이우선탐색을 한다. 이 때 방문한 노드는 노드1에서 갈 수 있는 노드이므로 인접행렬(배열 adj)에 표시해둔다.

시작점을 노드1부터 노드 N까지 반복한다. 그럼 모든 정점에 대해서 경로의 존재여부를 구할 수 있다.

문제는 깊이우선탐색(DFS)를 이용했다. DFS를 재귀로 많이 구현하는데, 재귀로 구현했다가 시간 초과가 나서 스택(Stack)으로 구현했다. 어차피 재귀도 스택이므로 방법이 크게 다른건 아니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <iostream> #include <stack> #include <vector>   #define MAX     100   using namespace std;   int n; int adj[MAX + 1][MAX + 1];   void DFS(int v) {     vector<int> visit(MAX + 1, 0);     stack<int> sp;       sp.push(v);       while (!sp.empty())     {         bool next = false;         for (int i = 1; i <= n; i++)         {             if (adj[sp.top()][i] && (visit[i] == 0))             {                 sp.push(i);                 visit[i] = 1;                 adj[v][i] = 1;                 next = true;                 break;             }         }         if(!next)             sp.pop();     } }   void input() {     cin >> n;     for (int i = 1; i <= n; i++)         for (int j = 1; j <= n; j++)             cin >> adj[i][j]; }   int main() {     input();       for (int v = 1; v <= n; v++)         DFS(v);       for (int i = 1; i <= n; i++)     {         for (int j = 1; j <= n; j++)             cout << adj[i][j] << " ";         cout << endl;     }     return 0; }