글 읽기 - bfs 스페셜저지 시간복잡도

112ckek 4년 전 0

안녕하세요. 이 문제 시간복잡도에 궁금증이 생겨 질문드립니다.

제가 생각한 방법은 인접리스트로 입력을 받아서 list[from]을 여러번 돌면서 계속 체크하는 방법입니다.

입력과 일치하면 index가 n이 되고 그렇지 않으면 n이 아니게 되는 것으로 판별했습니다.

제 방식으로 한다면 만약 1에 모든 노드가 연결되어있다면 최대 N²의 시간복잡도가 나오는 것으로 보이는데 이 TC가

왜 통과하는지 궁금합니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> list[100001];
bool check[100001];
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b;
        list[a].push_back(b);
        list[b].push_back(a);
    }
    vector<int> v(n);
    int index = 0;
    for(int i = 0; i < n; i++) cin >> v[i];
    if(v[0] != 1){
        cout << 0 << '\n';
        return 0;
    }
    queue<int> q; q.push(v[index++]);
    check[v[0]] = true;
    while(!q.empty()){
        int from = q.front(); q.pop();
        int size = list[from].size();
        for(int i = 0; i < size; i++){
            if(check[list[from][i]]) continue;
            if(list[from][i] == v[index]){
                q.push(list[from][i]);
                check[list[from][i]] = true;
                index++;
                i = -1;
            }
        }
    }
    if(index == n) cout << 1 << '\n';
    else cout << 0 << '\n';
    return 0;
}

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

문제

문제

출처

ICPC

bfs 스페셜저지 시간복잡도

112ckek 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말