백준 11403번: 경로 찾기 (C++)

링크

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

풀이방법

해당 문제는 BFS를 응용하여 다음과 같은 스텝으로 문제를 해결하였다.

1. 우선 양방향 그래프가 아니고 특정 방향으로만 이동할 수 있는 방향 그래프이기 때문에 adj vector 배열 변수에 입력되는 순서로만 값을 대입하였다.
2. 문제에서 i에서 간선을 따라 갔을 때 j까지 갈 수 있으면 1을 출력하고 아니면 0을 출력하라고 했으므로 i에서 bfs를 시작해서 이동하다가 j를 만나는 순간 for문과 while문을 탈출하고 출력용 배열인 board에 1을 넣어준다.
3. 최종적으로 board 배열을 출력한다.

위 설명의 흐름대로 코드를 보면 무슨 말인지 이해할 수 있을것이다.

코드

#include <bits/stdc++.h>
using namespace std;


int board[105][105];
vector<int> adj[105];
int n;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int num;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> num;
            if (num == 1) adj[i].push_back(j);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int vis[105] = {0};
            bool flg = false;
            queue<int> q;
            q.push(i);
            while (!q.empty())
            {
                int cur = q.front();
                q.pop();
                for (auto nxt : adj[cur])
                {
                    if (nxt == j)
                    {
                        board[i][j] = 1;
                        flg = true;
                        break;
                    }
                    if (vis[nxt]) continue;
                    q.push(nxt);
                    vis[nxt] = true;
                }
                if (flg == true) break;
            }
            
        }
    }


    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
  
            cout << board[i][j] << ' ';
        }
        cout << '\n';
    }
}