KOITP 보물찾기

<링크>

https://koitp.org/problem/SDS_TEST_TREASURE/read/ 

<소스코드>

#include<stdio.h>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
vector<int> adj[1001];
queue<int> q;
int isVisited[1001];
int N,M,K;
int bfs();
int main()
{
    int T;
    scanf("%d",&T);
    for (int t = 1; t <= T; ++t)
    {
        for (int i = 0; i <= 1000; ++i)
            adj[i].clear();
        q = queue<int>();
        memset(isVisited, 0, sizeof(isVisited));
        scanf("%d%d%d", &N, &M, &K);
        for (int i = 0; i < M; ++i)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            adj[a].push_back(b);
        }
        int ans = bfs();
        printf("#%d ", t);
        if (ans)
            printf("%d\n", ans);
        else
            printf("-1\n");
    }
    
}
int bfs()
{
    
    q.push(1);
    int depth = 0;
    while (!q.empty())
    {
        int size = q.size();
        for (int i = 0; i < size; ++i)
        {
            int cur = q.front();
            q.pop();
 
            if (cur == N)
                return depth;
            int s = adj[cur].size();
            for (int i = 0; i < s; ++i)
            {
                int to = adj[cur][i];
                if (!isVisited[to])
                {
                    isVisited[to] = 1;
                    q.push(to);
                }
            }
        }
        ++depth;
        if (depth > K)
            return 0;
    }
    return 0;
}

<풀이>

BFS를 통해 목적지가 나오면 그 때의 depth가 답이다.

또한 depth가 K를 초과하면 더이상 탐색할 필요가 없고

모든 노드를 다 돌아봤음에도 목적지를 못찾으면 답은 -1이다.