11403번

11403번 - 경로 찾기

bfs를 돌려서 모든 점을 방문할 수 있을거라 생각하고 bfs로 시작했다. 

간선이 양방향이 아니란 점이 중요하고, 내 풀이 방식에서 시작점을 check 하지 않았다.

이는 예를 들어 0에서 0으로 돌아오는 것을 확인할 수 있도록 남겨두었다.

나는 i = 0 일때 bfs를 돌려서 갈 수 있는 체크 된 지점을 모두 1로 맵 세팅하고

i=1 일때 또 bfs를 돌려서 갈 수 있는 체크 된 지점을 모두 1로 세팅하는 방식으로 했다.

##플로이드-워샬 알고리즘이 편하다고 다른 사람들이 그러던데.. 공부를 더 해야겠다.

플로이드 워셜 알고리즘 정답 코드 2개 추가.

첫번째꺼는 최단거리를 구한 후 바꿔주는 코드이고, 두번째 코드는

플로이드 워셜 알고리즘에서 그냥 경로가 존재하는지 확일 할 때는 && 와 || 연산을 이용해서 풀 수 있다.

< 정답 코드 -bfs >

#include<iostream>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int N;
vector<int> v[101];
int map[101][101];
bool check[101];
int main()
{
 
 
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int tmp;
            cin >> tmp;
            if (tmp == 1)
            {
                v[i].push_back(j);
            }
        }
    }
 
    queue<int> q;
    for (int i = 0; i < N; i++)
    {
        memset(check, false, sizeof(check));
        q.push(i);
 
        while (!q.empty())
        {
            int now = q.front();
            q.pop();
 
            for (int i = 0; i < v[now].size(); i++)
            {
                int next = v[now][i];
                if (!check[next])
                {
                    check[next] = true;
                    q.push(next);
 
                }
            }
        }
 
        for (int j = 0; j < N; j++)
        {
            if (check[j])
            {
                map[i][j] = 1;
            }
            else
            {
                map[i][j] = 0;
            }
        }
 
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cout << map[i][j]<<" ";
        }
        cout << endl;
    }
    
 
 
 
 
    return 0;
}

<정답 코드 - 플로이드 워셜 알고리즘>

#include<iostream>
 
using namespace std;
int D[101][101];
const int INF = 987654321;
int main()
{
    
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &D[i][j]);
            if (D[i][j] == 0)
            {
                D[i][j] = INF;
            }
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (D[i][j] >= INF)
            {
                printf("0 ");
            }
            else
            {
                printf("1 ");
            }
        }
        puts("");
    }
 
    return 0;
}

<정답 코드 - 플로이드 워셜 알고리즘 단순 경로 존재 확인 >

#include<iostream>
 
using namespace std;
int D[101][101];
 
int main()
{
    
 
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &D[i][j]);
        }
    }
 
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                D[i][j] = (D[i][j] || (D[i][k] && D[k][j]));
 
            }
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d ", D[i][j]);
        }
        puts("");
    }
 
    return 0;
}