백준 s1 11403 경로 찾기 c++

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

11403번: 경로 찾기

 

문제

가중치가 없는 그래프의 인접행렬이 주어졌을 때,

i노드 -> j노드로 갈 수 있는지 나타내는 N*N 배열을 출력하기

갈 수 있으면 1, 그렇지 않으면 0

 

풀이

각 정점에서 시작해서 DFS로 방문할 수 있는 노드를 answer[시작정점][방문가능한정점] = 1로 둔다.

이때 방문할 수 있다 == 갈 수 있다이므로, 결국엔 DFS의 vis배열과 같게 된다.

 

수도 코드

for start: 1번 노드 ~ N번 노드
	dfs로 가는 경로 모두 vis[start]에 표시

 

이때 시작 노드는 vis = 1로 체크되면 안되므로, 코드 짤 때 편하려고 재귀 대신 비재귀(stack)방식을 사용했다.

 

전체 코드

/*boj s1 11403 경로 찾기*/
#include <iostream>
#include <stack>
#define MAXN 105
using namespace std;

int N;
int adj[MAXN][MAXN];
int vis[MAXN][MAXN];
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> adj[i][j];
        }
    }

    for (int start = 0; start < N; start++) {
        stack<int> S;
        S.push(start);

        while (!S.empty()) {
            int cur = S.top();
            S.pop();

            for (int i = 0; i < N; i++) {
                if (adj[cur][i] == 0) continue;
                if (vis[start][i]) continue;

                S.push(i);
                vis[start][i] = 1;
            }
        }
    }

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