글 읽기 - 단순히 BFS만 써서 풀 수 없나요..?

humor999 3년 전 2

BFS로 접근했습니다.

1. 입력받을 시 시작점(0)의 호선을 기억하기위해 row에 저장합니다.

앞으로 row는 현재 탐색중인 호선을 저장합니다..

2. row호선을 역을 순회하면서 각 역마다 환승가능한 호선이 있는지 chk()함수를 통해 확인합니다.

2.5 row호선을 순회하다가 M을 찾으면 cnt(환승횟수)를 저장하고 반환합니다.

3. chk()함수는 같은 호선이나 방문한 호선은 무시하고 같은 역이 있는 호선을 set에 담습니다.

4. set에 있는 호선을 꺼내 queue에 넣고 방문한 것으로 처리합니다.(bool v[])

위 방법대로 했습니다..

순환선 문제일것 같아서 몇 가지 반례를 만들어서 해봤는데도 뭐가 문젠지 잘 모르겠서요.

살려주새오..

반례

5
7 12 1 2 3 1 12 8
2 12 13
7 13 0 9 4 99 99 13
6 13 8 10 7 99 13
2 13 22
22

ans=1

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <utility>
#include <algorithm>
#include <tuple>
#include <string>
#include <cstring>
#include <list>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

ll N,M,ans=1e9,row,cnt;
vector<ll> vec[11];
bool v[11];


void chk(ll s, set<int>& t) {
    for(int i=1; i<=N ;i++) {
        // 3. 현재 호선이거나 방문한 호선은 무시.
        if(i==row || v[i]) continue;
        for(int j=0; j<vec[i].size(); j++) {
            if(vec[i][j]==s) {
                    t.insert(i);
            }
        }
    }
}


void go() {
    queue<ll> q;
    q.push(row);
    v[row]=true;

    while(!q.empty()) {
        int step=q.size();

        while(step--) {
            // 1. row는 현재 탐색중인 호선.
            ll row=q.front(); q.pop();
            for(int i=0; i<vec[row].size(); i++) {
                // 2.5 현재 호선에 목적지가 있는지 확인.
                if(vec[row][i]==M) {
                    ans=cnt;
                    return;
                }

                set<int> t;
                // 2. chk()에 현재 호선에서 i번째 역을 넘겨
                // 환승가능한 호선을 t에 얻어냄.
                chk(vec[row][i],t);
                if(!t.empty()) {
                    for(auto ele:t) {
                        // 4. set에있는 호선을 Q에 넣고 방문처리.
                        q.push(ele);
                        v[ele]=true;
                    }
                }
            }
        }
        cnt++;
    }
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>N;
    for(int i=1; i<=N; i++) {
        int t{},a{};
        cin>>t;
        while(t--) {
            cin>>a;
            vec[i].emplace_back(a);
            if(a==0) row=i;
        }
    }
    cin>>M;
    go();

    if(ans==1e9) ans=-1;
    cout<<ans<<endl;

    return 0;
}

sait2000 3년 전 2

서울역이 환승역이면 어떡해요?

humor999 3년 전 2

@sait2000 답변 감사합니다.

그렇다면 몇호선에 있는 서울역을 이용했느냐에 따라 답이 달라지지 않나요??

예를들어 다음과 같은 입력에서

3
1 0
2 0 3
2 3 8
8

1호선의 서울역을 처음 탔으면 답은 2이지만 2호선에서 서울역을 타면 1이 나옵니다.

문제에서는 몇호선에있는 서울역을 처음 이용한다고 제시되어있지 않아보이고..

위의 문제때문에 서울역을 유일하다는 게 암묵적인 정보인거 같기도 합니다.

humor999 3년 전 2

해결했습니다.

윗 분 말대로 서울역이 환승역일 때 최소값을 내놓으면 되네요.

다음 반례 참고하시면 됩니다.

3
2 0 9
2 0 3
2 3 8
9

ans:0

3
1 0
2 0 3
2 3 8
8

ans:1

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

문제

문제

출처

ICPC

단순히 BFS만 써서 풀 수 없나요..?

humor999 3년 전 2

sait2000 3년 전 2

humor999 3년 전 2

humor999 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말