글 읽기 - 반례가... 있을까요..??

dntjd292 1년 전 0

있을 부분이 딱히 없어 보이는데... 16퍼에서 틀리네요..

답변 미리 감사드립니다.!!

#include <iostream>
#include <vector>

using namespace std;

vector<int> gp[104];

bool visited[104];

int n, m, num, a, b, c, d;

int cnt = 0;
int ans;
bool flag = 1;
void dfs(int idx)
{  
    visited[idx] = 1;
    for(auto &el : gp[idx])
        if(!visited[el])
        {
            cnt++;
            if(el == d)
            {
                ans = cnt;
                flag = 0;
                return;
            }
            dfs(el);
        }
    return;
}


int main()
{
    cin >> n;
    cin >> c >> d;
    cin >> num;
    for(int i=0; i < num; i++)
    {
        cin >> a >> b;
        gp[a].push_back(b);
        gp[b].push_back(a);
    }

    dfs(c);
    if(flag)
        cout << -1 << endl;
    else 
        cout << ans << endl;

    return 0;
}

hych0502 1년 전 1

증가시킨 cnt를 다시 감소시키는 부분이 빠진 것 같습니다. 이 부분이 없으면 끝부분을 만날때 마다 cnt가 증가된 것이 의도치 않게 남게 됩니다.

dntjd292 1년 전 0

우선 답변 감사합니다!

아래와 같이 백터에 저장 후 front 부분만 출력하면 답변해주신 cnt의 감소 기능을 대체할 수 있을것 같은데... 똑같이 16퍼에서 틀린 결과라고 나오네요...

#include <iostream>
#include <vector>

using namespace std;

vector<int> gp[104];

bool visited[104];

int n, m, num, a, b, c, d;

int cnt = 0;
vector<int> ans;
bool flag = 1;
void dfs(int idx)
{  
    visited[idx] = 1;
    for(auto &el : gp[idx])
        if(!visited[el])
        {
            cnt++;
            if(el == d)
            {
                ans.push_back(cnt);
                flag = 0;
                return;
            }
            dfs(el);
        }
    return;
}


int main()
{
    cin >> n;
    cin >> c >> d;
    cin >> num;
    for(int i=0; i < num; i++)
    {
        cin >> a >> b;
        gp[a].push_back(b);
        gp[b].push_back(a);
    }

    dfs(c);
    if(flag)
        cout << -1 << endl;
    else 
        cout << ans.front() << endl;

    return 0;
}

hych0502 1년 전 1

힌트를 좀 더 드리자면 처음 올리신 소스에다가

cnt--;

이 한 줄만 특정한 곳에 넣어주면 정답이 됩니다.

dntjd292 1년 전 0

감사합니다.

위에서 말씀해주신 것 처럼 그래프의 끝점에 다다를 경우 감소를 시켜주었더니 정답처리가 되네요..

덕분에 해결했습니다!!

#include <iostream>
#include <vector>

using namespace std;

vector<int> gp[104];

bool visited[104];

int n, m, num, a, b, c, d;

int cnt = 0;
int ans;
bool flag = 1;
void dfs(int idx)
{  
    visited[idx] = 1;
    for(auto &el : gp[idx])
        if(!visited[el])
        {
            cnt++;
            if(el == d)
            {
                ans = cnt;
                flag = 0;
                return;
            }
            dfs(el);
            // 그래프의 끝점에 다다를 경우 감소
            cnt--;
        }
    return;
}


int main()
{
    cin >> n;
    cin >> c >> d;
    cin >> num;
    for(int i=0; i < num; i++)
    {
        cin >> a >> b;
        gp[a].push_back(b);
        gp[b].push_back(a);
    }

    dfs(c);
    if(flag)
        cout << -1 << endl;
    else 
        cout << ans << endl;

    return 0;
}

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

문제

문제

출처

ICPC

반례가... 있을까요..??

dntjd292 1년 전 0

hych0502 1년 전 1

dntjd292 1년 전 0

hych0502 1년 전 1

dntjd292 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말