백준 11403 / 경로 찾기

말 그대로 경로를 찾는 문제다.

진짜 기초적인 그래프 문제

DFS와 BFS를 사용하여 풀 수 있다.

DFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;
 
int d[101];
int ans[101][101];
int arr[101][101];
int n;
vector<vector<int>> a;
 
 
void check(int num, int now) {
    
 
    for (int i = 0; i < a[now].size(); i++) {
        int x = a[now][i];
 
 
        if (d[x] == 0) {
            d[x] = -1;
            ans[num][x] = 1;
            check(num,x);
 
 
 
        }
 
    }
 
    return;
 
}
int main() {
    
    //freopen("Text.txt", "r", stdin);
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        vector <int> tmp;
        a.push_back(tmp);
 
    }
 
 
    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++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) {
                a[i].push_back(j);
            }
 
        }
    }
 
    for (int i = 0; i < n; i++) {
        check(i,i);
        memset(d, 0, sizeof(d));
    }
 
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
 
 
}
 
 

BFS

#include <stdio.h>
#include <iostream>
#include <queue>
#include <vector>
#include <memory.h>
using namespace std;
 
int d[101];
int ans[101][101];
 
int main() {
    
    //freopen("Text.txt", "r", stdin);
    int n;
    int arr[101][101];
 
    
    queue <int> q;
    vector<vector<int>> a;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        vector <int> tmp;
        a.push_back(tmp);
 
    }
 
 
    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++) {
        for (int j = 0; j < n; j++) {
            if (arr[i][j] == 1) {
                a[i].push_back(j);
                //a[j].push_back(i);
            }
 
        }
    }
 
 
    for (int i = 0; i < n; i++) {
        q.push(i);
 
 
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int j = 0; j < a[x].size(); j++) {
                if (d[a[x][j]] == 0) {
                    d[a[x][j]] = -1;
 
                    ans[i][a[x][j]] = 1;
                    q.push(a[x][j]);
                }
            }
 
        }
 
        memset(d, 0, sizeof(d));
 
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
 
}