경로찾기 #11403 c++ 풀이

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

11403번: 경로 찾기

유난히도 이해가 잘 안됐던 문제

단어에 꽂히면 문제가 잘 안풀리는 것 같다.

i->j 로 갈수 있는지 단방향 그래프에 관해서 묻는 문제였다.

따라서 최근 bfs문제를 많이 풀어서 그런지 bfs 알고리즘으로 접근하였다

문제 카테고리는 플로이드 워셜 알고리즘이라고 표시가 되어있긴 했다.

 

bfs로 순회시키고, 방문했던 경로를 저장한 visited 배열을 다시 순회하여, 해당 정점부터 표시된 곳까지 1로 칠해주면 된다.

#include <iostream>
#include <queue> // use bfs algorithm
#include <cstring> // use memset

#define MAX_SIZE 100 

using namespace std;
int graph[MAX_SIZE][MAX_SIZE];
int ans[MAX_SIZE][MAX_SIZE];
int visited[MAX_SIZE];
int N; 


void bfs(int start) {
    
    queue<int> q;
    q.push(start);
    //visited[start] = 1;
    //ans[start][0] = 1;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int i = 0; i < N; i++) {
            if (graph[curr][i] == 1 && visited[i] == 0) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
   
}

int main() {
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> graph[i][j];
            //graph[j][i] = gra
        }
    }
    //for (int i = 0; i < N; i++) {
    //    for (int j = 0; j < N; j++) {
    //        if (graph[i][j])graph[j][i] = 1;
    //        //graph[j][i] = gra
    //    }
    //}
    for (int i = 0; i < N; i++) {
        memset(visited, 0, sizeof(visited));
        bfs(i);
        for (int j = 0; j < N; j++) {
            if (visited[j] == 1) {
                ans[i][j] = 1;

            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << ans[i][j]<<" ";

        cout << "\n";
    }
    return 0;
}