티스토리 뷰
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; } |