[백준] 11403 - 경로 찾기, C++

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

11403번: 경로 찾기

 본 문제는 배열을 인접행렬로 바꿔서 풀어야 하는 문제다. 그래프에서 배열로 경로탐색을 하는것 보다 인접행렬로 탐색을 하는것이 빠르다.

1. 입력된 배열을 인접행렬로 변경
2. 간선 방문 여부 확인하며 탐색

#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
vector<int> v[101];
bool chk[100][100];
 
bool cal(int now, int fin) {
    queue<int> q;
    q.push(now);
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int i = 0; i < v[node].size(); i++) {
            int next = v[node][i];
            if (!chk[node][next]) {
                // 다음 노드가 목표 노드와 동일할 경우
                if (next == fin) return true;
                chk[node][next] = true;
                q.push(next);
            }
        }
    }
    return false;
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int tmp;
            scanf("%d", &tmp);
            if (tmp == 1) v[i].push_back(j);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            // 방문한 간선 초기화
            memset(chk, false, sizeof(chk));
            if (cal(i, j)) printf("1 ");
            else printf("0 ");
        }
        printf("\n");
    }
    return 0;
}