• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

64번에서 ch 배열 다시 0으로 초기화 하지 않는것에 관련하여 질문 있습니다!

22.08.19 15:54 작성 조회수 169

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으로 변경하지 않았습니다. 제 생각처럼 콜바이 밸류기 때문에 값이 변경되지 않으니 방문했던 정점을 초기화 할 필요가 없는게 맞는지 아니면 다른이유인지 궁금합니다! 정답은 모두 맞게 나옵니다!!

답변 1

답변을 작성해보세요.

0

안녕하세요^^

네. 맞습니다. 콜바이밸류로 넘겼기 때문에 이전 함수로 백을 할 때 이전 벡터상태로 자동으로 되돌아갑니다.

만약 vector<bool> &visit 이렇게 콜바이레퍼런스로 매개변수를 만들었다면 꼭 이전함수로 백을 할 때 visit를 false로 해주어야 합니다.