[BOJ] #11403 경로 찾기

시간 제한	메모리 제한	정답 비율
1 초	256 MB	51.358%

 

11403번: 경로 찾기

 

해결방안

각 정점에 대해 연결되어 있는 정점으로 DFS로 탐색하면서 지나갔다면 arr[i][j] 를 1로 바꾼다. 지나가지 않았던 정점에 대해서만 탐색을 계속 이어간다. 각 정점에 대해 연결되어 있는 정점의 정보를 알고 싶으므로 n 번 반복하면 모든 정점의 정보를 알 수 있다.

메모리	시간
2268 KB	0 ms

#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
#define F(x,y,u,p) for(int x = 0; x<u; x++)for(int y = 0; y<p; y++)
int n, arr[105][105];
vector<vector<int>> v;
void dfs(int start, int present) {
    for (auto& e : v[present]) {
        if (arr[start][e]) continue;
        arr[start][e] = 1;
        dfs(start, e);
    }
}
int main() {
    scanf("%d", &n);
    v.resize(n * n);
    int a;
    F(i, j, n, n) {
        scanf("%d", &a);
        if (a) v[i].push_back({ j });
    }
    for (int i = 0; i < n; i++) {
        dfs(i, i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", arr[i][j]);
        }
        printf("\n");
    }
    return 0;
}