글 읽기 - 테스트 케이스는 다 맞는데 뭐가 문제인지 모르겠습니다 ㅠㅠ

spqjf12345 2년 전 0

node 벡터에 시작 위치, 정점 위치, 거리 순으로 넣어

방문하지 않은 node인 경우 queueq에 넣어 depth 값을 증가시켜줬는데요

for문 안에 if문으로 K랑 비교하는 부분에서 뭔가 로직이 잘못된듯 하고 아닌 듯 하고 왜 틀린지 잘 모르겠습니다 ..

//
//  18352_city_kDistance.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/09/02.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N, K, X, M;
vector<pair<int, int>> node[300001]; // start, end, min_distance
queue<int> q;
bool visit[300001] = {false, };
vector<int> answer;


//도시를 출력
void find_kDistance(){
    // x == start
    q.push(X);
    visit[X] = true;
    int depth = 0;
    
    while(!q.empty()){
        int next = q.front();
        
        q.pop();
        depth++;
        
        for(int i = 0; i < node[next].size(); i++){
            
            if(visit[node[next][i].first] == false){
                visit[node[next][i].first] = true;
                q.push(node[next][i].first);
                
                node[next][i].second = depth;
                if(node[next][i].second == K) { answer.push_back(node[next][i].first); } // 깊이가 같다면
                
            }

        }
    }
    
    //정답 계산
    if(answer.size() == 0){
        cout << "-1" << '\n';
    }else {
        for(int i = 0; i < answer.size(); i++){
            cout << answer[i] << '\n';
        }
    }
    
   
}

int main(){
    cin >> N >> M >> K >> X;
    
    for(int i = 0; i < M; i++){
        int A, B;
        //start -> end A, B, distance = 0
        cin >> A >> B;
        node[A].push_back({B, 0});
    }
    
    find_kDistance();
    return 0;
    
}

yous 2년 전 1

문제의 예제를 생각했을 때 node[1]에 {2, 0}, {3, 0}이 있을 텐데, queue에서 꺼낼 때마다 depth가 증가하면 node[1]에 {2, 1}, {3, 2}가 들어가게 됩니다. {2, 1}, {3, 1}이 들어가야 합니다.

queue에서 depth를 관리할 때 아래처럼 할 수 있습니다. 그러면 이중 while문에서 queue에 넣은 값은 depth 값이 증가할 때까지 꺼내지 않습니다.

이렇게 하게 되면 depth가 K인 모든 요소를 한번에 볼 수 있으므로 depth가 K인 경우를 다 처리하면 break 하면 됩니다.

int depth = 1;
while (!q.empty()) {
    int sz = q.size(); // 현재 depth에 해당하는 queue 원소 개수
    while (sz-- > 0) {
        int p = q.front();
        q.pop();
        for (int i = 0; i < node[p].size(); i++) {
            // 여기에서 q.push(...)로 들어간 원소는 depth + 1에 해당한다.
        }
    }
    if (depth == K) {
        break;
    }
    depth++;
}

yous 2년 전 1

위 코드에서 depth, depth + 1이라고 썼는데 위에서 depth = 1을 했으니 각각 depth - 1, depth가 맞겠네요. 적절히 바꾸시면 될 거 같습니다.

spqjf12345 2년 전 0

와 그런 문제점이 있었군요 .. 생각도 못했는데 정말 감사합니다 !!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

테스트 케이스는 다 맞는데 뭐가 문제인지 모르겠습니다 ㅠㅠ

spqjf12345 2년 전 0

yous 2년 전 1

yous 2년 전 1

spqjf12345 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말