백준 알고리즘 11403번 경로 찾기 C언어

문제

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

출력

총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.

문제 풀이

처음에는 문제 자체를 이해할 수 없었다.  이게 circle되는 개수를 구하라는 것 같기도 하고,,

 

방향 그래프이므로 1에서 2로 가는 길 따로 2에서 1가는 길 따로이다.

 

입력 그래프가 아래와 같이 주어진 경우

0 1 0  : 1 - 1(X),  1 - 2(O), 1 - 3(X)

0 0 1  : 2 - 1(X),  2 - 2(X),  2 - 3(O)

1 0 0  : 3 - 1(O),  3 - 2(X),  3 - 3(X)

 

1에서 2로 갈 수 있고, 2에서 3으로 갈 수 있으므로 1에서 3으로 갈 수 있다. 라는 규칙이 성립된다.

 

do_dfs 함수에서 target은 기준 노드가 되고 v는 확인 노드?가 된다.

위의 밑줄에서 예를 들자면 target은 1번이 되고

v인 2번은 1번(target)에서 3번으로 가는 길이 있는지 확인하는 중간 노드가 된다.

만약 3번이 다시 4번과 연결되는 노드가 있었다면 3번도 1번과 4번 사이 노드를 확인하는 중간 노드가 된다.

 

solution 함수에서 do_dfs 함수로 보내는 target값이 한 번씩 바뀔 때마다 visited 배열을 리셋한다.

리셋하지 않으면 target값이 바뀌었을 때 기존 target 값에 따른 방문 여부 visited 배열이 그대로 와서 원치 않는 결과를 얻는다.

 

#include<stdio.h>
#include<string.h>
#define SZ 101
 
int N;
int map[SZ][SZ];
int visited[SZ][SZ];
int ans_map[SZ][SZ] = { 0 };
 
void do_dfs(int target, int v) {
    for (int i = 1; i <= N; i++) {
        // v에서 i로 가는 길도 있고 한번도 방문하지 않은 경우
        if (map[v][i] == 1 && visited[v][i] == 0) {
            ans_map[target][i] = 1;
            visited[v][i] = 1;
            do_dfs(target, i);
        }
    }
}
 
void solution() {
    for (int i = 1; i <= N; i++) {
        memset(visited, 0, sizeof(visited));
        do_dfs(i, i);
    }
}
 
 
 
int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &map[i][j]);
        }
    }
 
    solution();
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            printf("%d ", ans_map[i][j]);
        }
        printf("\n");
    }
}