[BOJ 11403 // C++] 경로 찾기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11403번 문제인 경로 찾기이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/11403

11403번: 경로 찾기

이 문제는 주어진 인접행렬(adjacency matrix)을 보고 각 node가 연결되어있는지 아닌지를 확인하는 문제이다.

 

node의 수가 충분히 적으므로, 단순하게 행렬을 제곱하는 방식으로 풀어보았다. (이 방법이 가장 빠른 방법인 것은 아니다.)

 

adjacency matrix를 transpose하고 n제곱한 뒤 다시 transpose를 해 얻을 수 있는 행렬의 i행 j열 성분은 i번째 node에서 j번째 node로 가는 길이 n인 경로의 경우의 수와 같다. 이 값이 0이 아니라면 n번만에 node i에서 node j로 가는 경로이 있다는 것이므로 이에 대응되는 답안의 출력을 1로 한다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using std::cin;
using std::cout;

int mat[100][100];
int expmat[100][100];
int tmp[100][100];
int ans[100][100];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    int x;

    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cin >> x;
            mat[j][i] = x; // adjacency matrix의 transpose를 저장
            if (i == j) expmat[i][j] = 1; // identity matrix
        }
    }

    for (int _ = 0;_ < N;_++) {
        for (int i = 0;i < N;i++) {
            for (int j = 0;j < N;j++) {
                for (int k = 0;k < N;k++) {
                    tmp[i][j] += mat[i][k] * expmat[k][j];
                }
            }
        }
        for (int i = 0;i < N;i++) {
            for (int j = 0;j < N;j++) {
                expmat[i][j] = tmp[i][j];
                if (tmp[i][j] != 0) { // N번만에 i에서 j로 가는 경로가 있다면
                    ans[i][j] = 1; // 일단 저장
                }
                tmp[i][j] = 0;
            }
        }

    }
    for (int i = 0;i < N;i++) {
        for (int j = 0;j < N;j++) {
            cout << ans[j][i] << ' '; // adjacency matrix는 다시 transpose해줘야 한다.
        }
        cout << '\n';
    }

    return 0;
}