글 읽기 - 해당 문제를 BFS로 접근했는데 잘못된 걸까요?

spparty 1년 전 0

주어진 루트에서 처음부터 그 다음 루트로 가는 길이 각각 존재한다면 처음부터 끝까지 도달할 수 있다는 가정하에 BFS로 풀어보았습니다.

TC는 맞았는데 어느 부분에서 오류가 있는지 궁금합니다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N, M;    // N 도시, M 여행 계획에 속한 도시
int graph[201][201] = {0, };
vector<bool> visited(201, false);
int route[1001] = {0, };
int start, dest;
// BFS로 접근
bool BFS(int start, int dest, vector<bool> visited)
{
    queue<int> q;
    visited[start] = true;  // 방문 처리
    q.push(start);
    while (!q.empty())
    {
        int qSize = q.size();
        for (int i=0; i<qSize; i++)
        {
            int qfront = q.front();
            if (qfront == dest) // 경로가 있으면 true 반환
                
                return true;

            for (int j=1; j<=N; j++)
            {
                if (graph[qfront][j] != 0 && !visited[j])   // 연결되고 방문하지 않았으면
                {
                    q.push(j);
                    visited[j] = true;
                }
            }
            q.pop();
        }
    }
    return false;  
}

int main()
{
    cin >> N;
    cin >> M;
    for (int i=1; i<=N; i++)
    {
        for (int j=1; j<=N; j++)
        {
            cin >> graph[i][j];
        }
    }
    for (int i=0; i<M; i++)
    {
        cin >> route[i];
    }
    // 매 start, dest를 검사한다.
    for (int i=0; i<M-1; i++)
    {
        if (!BFS(route[i], route[i+1], visited))
        {
            cout << "No";
            break;
        }
        if (i == M-2)
            cout << "Yes";
    }
}

pill27211 1년 전 1

출력하실 때 No -> NO, Yes -> YES 입니다.

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

문제

문제

출처

ICPC

해당 문제를 BFS로 접근했는데 잘못된 걸까요?

spparty 1년 전 0

pill27211 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말