it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

64. 경로탐색 (그래프 DFS : Depth First Search)

257

0

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int cnt = 0;

int dfs(int n,int start,  vector<vector<int> > mtrx, vector<bool> visit)//visit벡터를 콜바이 밸류로 받아오기 떄문에 값이 변하지 않음
{
    
    if (start == n)
    {
        cnt++;
    }
    else
    {
        visit[start] = true;

        for (int i = 1; i <= n; i++)
        {
            if (mtrx[start][i] == 1 && visit[i] == false)
            {
                dfs(n, i, mtrx,  visit);//이 함수를 빠져나왔을 경우 들어가기 직전의 visit 벡터를 갖고 있으므로 다시 방문하지 않았다는 표시를 해줄 필요없음
            }
        }
    }
    
    return cnt;
}

 

int main()
{
    int n, m;
    int n1, n2;

    cin >> n >> m;
    vector<bool> visit(n+1, false);//방문했던 지점인지 체크하기위해서
    vector<vector<int> > mtrx(n + 1, vector<int>(n + 1, 0));//n+1/n+1 크기의 행렬을 0으로 초기화

    for (int j = 1; j <= m; j++)
    {
        cin >> n1 >> n2;
        mtrx[n1][n2] = 1;//인접행렬 생성
    }
    
    int count = dfs(n, 1, mtrx,visit);
    cout << count;
}

.안녕하십니까 64번문제 ch[]를 초기화 하는 부분에 대한 제 생각이 맞는 생각인지 의문이 들어 질문을 남기게 되었습니다.

저는 ch배열을 전역변수로 설정하지 않고 visit 벡터로 생성하여 dfs 함수에 콜바이 밸류로 넘겨주었습니다 이 때 선생님의 코드에서는 visit벡터 즉 강의에서 ch배열을 다시 0으로 초기화 해주는 부분이 있는데 제 생각으로는 콜 바이 밸류기 때문에 dfs함수가 다시 호출될 때 visit 벡터값이 변경되어 적용되는 것이 아니므로 원래 함수로 복귀했을때는 기존은 visit 벡터를 갖고 실행된다고 생각하여 저는 방문한 정점을 다시 0으로 변경하지 않았습니다. 제 생각처럼 콜바이 밸류기 때문에 값이 변경되지 않으니 방문했던 정점을 초기화 할 필요가 없는게 맞는지 아니면 다른이유인지 궁금합니다! 정답은 모두 맞게 나옵니다!!

C++ 코테 준비 같이 해요!

답변 1