[C++] 삼성 SDS KOITP 보물찾기

문제링크 : https://koitp.org/problem/SDS_TEST_TREASURE

[삼성 SDS 대학생 알고리즘 특강 사전 테스트 B Type 1번 문제]

DFS로 풀게되면 무조건 시간초과가 나게되서 BFS로 풀어야하는 문제이다.

최단거리를 찾는 동시에 이동한 거리를 dist 배열을 따로 만들어서 별도로 저장했다.

// KOITP_SDS_Btype_01
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    // freopen("../input.txt", "r", stdin);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int ruin, numOfClue, remain, result;
        cin >> ruin >> numOfClue >> remain;
        vector<vector<bool>>clue(ruin + 1, vector<bool>(ruin + 1, false));
        vector<bool>visited(ruin + 1, false);
        vector<int> queue;
        vector<int> dist(ruin+1);
        int input1, input2;
        for (int i = 0; i < numOfClue; i++) {
            cin >> input1 >> input2;
            clue[input1][input2] = true;
        }
        visited[1] = true;
        dist[1] = 0;
        queue.push_back(1);
 
        while(!queue.empty()){
            int cur = queue.front();
            queue.erase(queue.begin());
            for(int i = 1; i <= ruin; i++){
                if(clue[cur][i] && !visited[i]){
                    visited[i] = true;
                    dist[i] = dist[cur] + 1;
                    queue.push_back(i);
 
                    if(i == ruin)
                        goto OUT;
                }
            }
        }
        OUT:
        result = dist[ruin] == 0 || dist[ruin] > remain? -1 : dist[ruin];
 
        cout << "#" << t << " " << result << "\n";
    }
    return 0;
}