핵심 아이디어

<aside> 💡

$dp_{ij} = 0$ : $j$번째 시행에 정점 $i$에 도달할 수 없다.

$dp_{ij} = 1$ : $j$번째 시행에 정점 $i$에 도달할 수 있다.

$dp_{ij}$는 $i$와 연결된 모든 정점 $k$에 대해서 $dp_{kj-1} = 1$인 $k$가 하나라도 존재하면 $1$ 아니면 $0$.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

int n, m, x, y;
bool isC[1'001][1'001];
vector<int> adj[1'001];

int dp[1'001][1'001];

int go(int idx, int cnt)
{
    int &ret = dp[idx][cnt];
    if(ret != -1) return ret;

    ret = 0;
    for(int nxt: adj[idx]){
        if(go(nxt, cnt-1)){
            ret = 1;
            break;
        }
    }

    return ret;
}

signed main()
{
    FASTIO;
    cin >> n >> m >> x >> y;
    for(int i = 0; i<m; i++){
        int x, y;
        cin >> x >> y;
        if(!isC[x][y] && !isC[y][x]){
            isC[x][y] = true;
            isC[y][x] = true;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }

    memset(dp, -1, sizeof(dp));
    for(int i = 1; i<=n; i++) dp[i][0] = 0;
    dp[x][0] = 1;

    bool flag = false;
    for(int i = 1; i<=n; i++){
        if(go(i, y)){
            cout << i <<" ";
            flag = true;
        }
    }

    if(!flag){
        cout << "-1\\n";
    }
    
    return 0;
}