[DFS] 백준 16947번 서울 지하철 2호선(C++)

https://www.acmicpc.net/problem/16947

 

내가 문해력이 떨어지는건지.. 너무 문제부터 이해하기 어려웠다

이게뭐야 이런

ㅡㅡ;;

 

잘 찾아보니까

 

앞선 graph처럼 노드들이 연결되어 있을때

순환하는 친구하고 순환하지 않은 친구 구별하는 것 +

순환하지 않는 친구의 순환하는 곳 까지의 거리

 

를 구하면 되는 것!

 

 

즉

 

예시 입력과 출력에 나온 건데

 

1,2,3의경우 "순환"하고 있고

 

5  4 6은 순환하지 않고 있다

 

이때 여기서

 

1 2 3 은 순환하는 역 까지의 거리가 0(자기자신)이니까 0이 출력되고

 

5 ,4 6 의 경우는 1 1 2 가 출력되는 것이다(제일 가까운 3까지의 거리가)

 

[DFS,BFS] 백준 16929번 Two Dots(C++)

[DFS,BFS] 백준 16929번 Two Dots(C++)

 

저번문제 two dots하고 유사한데 문제는 거리까지 구해야 되네././.

 

먼저 !

 

나는

 

그 역이 순환역인가 아닌가?를 구별해주고

 

그 후 순환하는 역이 아닌 경우, 거리를 찾아주는 dfs식을 한 개씩 총 두 개 만들었다

 

 

#include <iostream>

#include <queue>

#include <vector>

#include <string>

#include <algorithm>

bool visited[3001];

bool visited2[3001];

int n, m;

bool is_find = false;

bool is_circle[3001];

using namespace std;

vector<int> v[3001];

void dfs(int x, int depth);

void dfs_2(int x, int depth);

void init();

int start;

int Dep;

int main()

{

    cin >> n;

    for (int i = 0; i < n; i++)

    {

        int node_a, node_b;

        cin >> node_a >> node_b;

        v[node_a].push_back(node_b);

        v[node_b].push_back(node_a);

    }

    for (int i = 1; i <= n; i++)

    {

        start = i;

        dfs(i, 0);

        if (is_find)

            is_circle[i] = true;

        else

            is_circle[i] = false;

        is_find = false;

        init();

    }

    for (int i = 1; i <= n; i++)

    {

        if (!is_circle[i])

        {

            visited2[i] = true;

            Dep = 9999999;

            dfs_2(i, 0);

            cout << Dep << " ";

        }

        else

            cout << "0 ";

        init();

    }

}

void init()

{

    for (int i = 1; i <= n; i++)

    {

        visited[i] = false;

        visited2[i] = false;

    }

}

void dfs(int x, int depth)

{

    visited[x] = true;

    for (int i = 0; i < v[x].size(); i++)

    {

        if (!visited[v[x][i]])

        {

            visited[v[x][i]] = true;

            dfs(v[x][i], depth + 1);

            visited[v[x][i]] = false;

        }

        else if (v[x][i] == start && depth >= 2)

            is_find = true;

    }

}

void dfs_2(int x, int depth)

{

    if (is_circle[x])

    {

       

        Dep = min(Dep, depth);

        return;

    }

    for (int i = 0; i < v[x].size(); i++)

    {

        if (!visited2[v[x][i]])

        {

            visited2[v[x][i]] = true;

            dfs_2(v[x][i], depth + 1);

            visited2[v[x][i]] = false;

        }

    }

}

 

좀 복잡한거 같긴 한데

 

내가 궁금해던 건..

void dfs_2(int x, int depth)

{

    if (is_circle[x])

    {

       

        Dep = min(Dep, depth);

        return;

    }

    for (int i = 0; i < v[x].size(); i++)

    {

        if (!visited2[v[x][i]])

        {

            visited2[v[x][i]] = true;

            dfs_2(v[x][i], depth + 1);

            visited2[v[x][i]] = false;

        }

    }

}

 

Dep = min(Dep, depth);

 

 

이부분이다..

이거 사실 Dep=depth해도 문제가 없더라고.,?

근데 왜 문제가 없는진 모르겠는데.. 그냥 애매한 테스트 케이스가 없어서 그런거 같더라구

화이팅