백준 11403:경로찾기

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

백준 11403 경로찾기 문제입니다.

이번 문제의 알고리즘은 만약 A->B->C->D 그래프가 있다면 A에서 D로 갈 수 있다는 것을 확인하면 되는데요, 이것을 확인하기 위해서 범위를 점점 좁혀가면서 탐색을 하는 방법으로 코딩하였습니다.

예를 들면 A->D로 이동할 수 있다면 B->D로 이동할 수 있는지 확인하면되고 또 이것을 확인하려면 C->D로 이동가능한지 확인하면 됩니다! 결과적으로 A->D로 이동할 수 있다는 결론이 나와요!

밑에는 제 코드입니다.

#include <stdio.h>
#include <stdbool.h>
 
#define MAX 20005
 
int G[MAX][MAX];
bool visited[MAX];
int N;
 
bool dfs(int cur, int target) {
    visited[cur] = true;
    if (G[cur][target]) {  //현재위치에서 목표점까지 갈 수 있으면
        return true;       //true 리턴
    }
    else {
        for (int i = 0; i < N; i++) {
            if (G[cur][i] && !visited[i]) {  //i로의 길이 있고, 방문하지 않았으면
                if (dfs(i, target)) {        //i에서 목표점으로의 탐색
                    return true;             //갈 수 있다면 결과적으로 true리턴
                }
            }
        }
        return false;  //탐색이 끝나고도 target으로 갈 수 없다면 false리턴
    }
}
 
int main(void) {
    scanf("%d", &N);
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            int way;
            scanf("%d", &way);
            G[r][c] = way;
        }
    }
 
    for (int r = 0; r < N; r++) {
        for (int c = 0; c < N; c++) {
            if (dfs(r, c)) {
                fputs("1 ", stdout);
            }
            else {
                fputs("0 ", stdout);
            }
            for (int i = 0; i < N; i++) {
                visited[i] = false;
            }
        }
        puts("");
    }
 
    return 0;
}