[백준 11403번] 경로찾기 C++

www.acmicpc.net/problem/11403

11403번: 경로 찾기

 

i번째 숫자가 갈 수 있는 모든 목적지를 출력해주면 되는 문제였습니다.

 

(i -> k) 가 가능하고 (k -> j) 가 가능하다면 (i -> j )가 가능함을 출력하면 되는 문제였습니다.

i -> k -> j

 

지금까지 풀었던 dfs와 많이 달랐고 나중에 찾아보니 이런 문제를위한 알고리즘이 있는데 제가 아는 범위는 아니기때문에 dfs를 사용했습니다.

 

모든 시작점 i 를 대상으로 깊이 우선 탐색으로 깊~게 탐색한 후에 갈 수 있는 모든 목적지를 visit=true 처리했습니다.

이후 visit == true 된 목적지는 i가 전부 갈 수 있는 루트임을 입력된 배열에 표기했습니다.

 

풀다보니 시간복잡도가 O(N^3) 이 나왔는데 많아봤자 n ==100 이기때문에 가능하다 느꼈습니다.

 

 

 

#include <iostream>
#include <cstring>
 
using namespace std;
int n;
int arr[101][101];
bool visit[101];
 
 
void dfs(int curr) {
    //정석적인 dfs
    for (int i = 0; i < n; i++)
        if (arr[curr][i] && !visit[i]) {
            visit[i] = true;
            dfs(i);
        }
}
int main() {
    cin >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> arr[i][j];
    
    for (int i = 0; i < n; i++) {
        //모든 시작점으로부터 dfs수행
        //dfs하기 전 방문 이력을 초기화해줌
        memset(visit, false, sizeof(visit));
        dfs(i);
        for (int j = 0; j < n; j++) {
            //dfs결과 visit==true 된 모든 도작치 j 는 i가 갈 수 있는 루트
            if (visit[j]) arr[i][j] = 1;
        }
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << arr[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}