koitp SDS_TEST_TREASURE 보물찾기

문제 링크입니다: https://koitp.org/problem/SDS_TEST_TREASURE/read/

전형적인 BFS(Breadth First Search) 알고리즘 문제였습니다.

시작점과 도착점이 정해져 있고 단방향 그래프이기 때문에 BFS 알고리즘을 돌리고 도착점에 도달했을 때 제한시간 내 도착하면 경과시간을 반환하고 제한시간을 초과했다면 -1을 반환해주면 되는 문제였습니다.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 1000 + 1;

 

int N, M, K;

vector<int> graph[MAX];

 

//전형적인 BFS

int BFS(int nodeNum, int cnt)

{

        queue<pair<int, int>> q;

        bool visited[MAX] = { false };

        q.push({ nodeNum, cnt });

 

        while (!q.empty())

        {

                 int curNode = q.front().first;

                 int elapsedTime = q.front().second;

                 q.pop();

 

                 if (curNode == N && elapsedTime <= K)

                         return elapsedTime;

 

                 visited[curNode] = true;

 

                 for (int i = 0; i < graph[curNode].size(); i++)

                 {

                         int next = graph[curNode][i];

                         if (!visited[next])

                                 q.push({ next, elapsedTime + 1 });

                 }

        }

        return -1;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for (int i = 1; i <= test_case; i++)

        {

                 //벡터를 꼭 비워줘야합니다

                 for (int j = 0; j < MAX; j++)

                         graph[j].clear();

                 cin >> N >> M >> K;

 

                 for (int j = 0; j < M; j++)

                 {

                         int node1, node2;

                         cin >> node1 >> node2;

 

                         //단방향 그래프

                         graph[node1].push_back(node2);

                 }

 

                 cout << "#" << i << " " << BFS(1, 0) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~