CPP05

JUSTICE_DER·2023년 7월 26일

1. 2644 - BFS + 경로찾기

⏲ CPP - 코딩테스트

목록 보기

9/41

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

1. 2644 - BFS + 경로찾기

= 배열 하나를 더 놓기

2차원 배열의 초기화를 했는데,

이상한 값들이 들어가 있다..

왜????

찾아보니까.. 원래는 배열은 생성하면 0으로 초기화되는데
CPP는 당연히 그렇진 않고,
2차원 배열이라도 int visited[N][N] = {0, };
위처럼 넣으면 0으로 초기화 된다고 보았는데,
왠지 적용이 안되는 모습이다..

CPP 2차원 배열의 0 초기화
https://slaystudy.com/initialize-2d-array-c-to-zero/

위의 글에서 memset을 사용하여 초기화하였다.

시도

#include <iostream>
#include <queue>

#include <cstring>
 
using namespace std;

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

    int N;
    cin >> N;

    int A;
    int B;
    cin >> A;
    cin >> B;

    int T;
    cin >> T;

    int connection[N+1][N+1] = {0,}; //적용 안됨
    int visited[N+1][N+1] = {0, };
    memset(connection, 0, sizeof(connection));
    memset(visited, 0, sizeof(visited));

    int from, to;
    for (int i = 0; i < T; i++)
    {
        cin >> from;
        cin >> to;

        connection[from][to] = 1;
        connection[to][from] = 1;
    }

    int count = 0;
    queue<int> nextNode;
    nextNode.push(A);

    while (!nextNode.empty())
    {
        count++;

        int A = nextNode.front();
        nextNode.pop();
        if(A == to)
        {
            break;
        }

        for (int i = 1; i <= N; i++)
        {
            if (connection[A][i] == 1 && visited[A][i] == false)
            {
                visited[A][i] = count;
                visited[i][A] = count;

                nextNode.push(i);
            }
        }
    }

    int min = 100;
    for(int i=0;i<N; i++)
    {
        if((visited[B][i]!=0) && min>visited[B][i])
        {
            min = visited[B][i];
        }
    }

    cout << min << "\n";


    return 0;
}

BFS로 구현을 해보았다
연결된건 알겠고 BFS로 A로부터 B까지 최단거리를 구하긴 했는데,
위의 코드로는 해당 값이 A로부터 간 B의 값인지 알 수가 없었다..

DFS로는 경로를 찾기 쉽고, BFS로는 최단거리를 찾기 쉽다.
https://kk-eezz.tistory.com/23

BFS에서 최단거리를 찾기 위해선,
따로 자료구조를 활용해야만 한다.

BFS로 풀어보자

시도 2

#include <iostream>
#include <queue>
// #include <stack>

#include <cstring>

using namespace std;

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

    int N;
    cin >> N;

    int ans_From;
    int ans_To;
    cin >> ans_From;
    cin >> ans_To;

    bool connection[N + 1][N + 1]; // 적용 안됨
    bool visited[N + 1];           // 2차원배열인 간선이 아닌, 1차원 배열로 정점을 기준으로 하였다.
                                   // 중복된 정점을 통과하지 못하도록 한다.
    memset(connection, false, sizeof(connection));
    memset(visited, false, sizeof(visited));

    int T;
    cin >> T;

    int from, to;
    for (int i = 0; i < T; i++)
    {
        cin >> from;
        cin >> to;

        connection[from][to] = true;
        connection[to][from] = true;
    }

    queue<int> nextNode;
    nextNode.push(ans_From);

    int path[N + 1] = {
        0,
    };
    while (!nextNode.empty())
    {
        int num = nextNode.front();
        nextNode.pop();

        if (num == ans_To)
        {
            break;
        }

        for (int i = 1; i < N + 1; i++)
        {
            if (connection[num][i] && !visited[i])
            {
                visited[num] = true;
                path[i] = num;

                nextNode.push(i);
            }
        }
    }

    //도달하지 못한 경우
    if(path[ans_To]==0)
    {
        cout << -1 << "\n";
        return 0;
    }

    // 역추적

    int i = path[ans_To];
    int count = 0;
    while (true)
    {
        count++;
        if (i != ans_From)
        {
            i = path[i];
        }
        else
        {
            break;
        }
    }

    cout << count <<"\n";
    return 0;
}