글 읽기 - 이렇게 풀면 안되나요?

an3735297 2년 전 0

1 -> 2 -> 3 으로 이동한다고 하면

1->2

2->3

로 쪼개서 생각해서

1->2 으로 bfs 탐색이 가능하고

2->3 으로 bfs 탐색이 가능하면

여행갈수 있다. 이렇게 생각했습니다.

M개의 루트가 주어지면 M-1번 bfs 탐색을 하는 것입니다...

# include <iostream>
# include <vector> 
# include <queue>
# include <cstdio>

using namespace std;

# define MAX 201
int N,M;

vector<int> go[MAX];
int arr[1000];

bool can_go(int start, int end) {
    bool visited[MAX] = {0,};
    visited[start] = true;
    queue<int> q;
    q.push(start);

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        if (cur == end) return true;

        for (int next : go[cur]) {
            if (visited[next]) continue;
            visited[next] = true;
            q.push(next);
        }
    }

    return false;
}

void print_result() {
    if (M == 1) {
        if (arr[0] >= 1 && arr[0] <= N) {
            cout << "YES";
            return;
        }
        cout << "NO";
        return;
    }
    for (int i = 1; i < M; i++) {
        if (!can_go(arr[i-1], arr[i])) {
            cout << "NO";
            return;
        }
    }
    cout << "YES";
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    cin >> N >> M;
    for (int s = 1; s <= N; s++) {
        for (int e = 1; e <= N; e++) {
            int x; cin >> x;
            if (x == 0) continue;
            go[s].push_back(e);
        }
    }

    for (int i = 0; i < M; i++) 
        scanf("%d", &arr[i]);

    print_result();
    
}

uuta8280 2년 전 0

저도 그렇게 풀었는데 timeout이 나더라고요 O(m*n²)

문제 푸는 방법은 경로가 같은 그래프에 속하는지 확인하면 간단히 풀리는 것 같습니다 O(n²)

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

문제

문제

출처

ICPC

이렇게 풀면 안되나요?

an3735297 2년 전 0

uuta8280 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말