오늘의 공부

programmers.co.kr/learn/courses/30/lessons/43162

깊이 우선 탐색(DFS)의 방식으로 풀었다.

stack을 이용해서 갈 수 있는 점으로 진행하다가 갈 수가 없으면 stack을 pop해서 이전의 점으로 돌아간다.

bool (check)를 이용해 방문한 컴퓨터는 true로 바꿔 주었으며 

다시 이전으로 돌아가야 하는 조건을 설정하는 부분에서 (if (!Find) 부분) 스택이 비어있다면 하나의 네트워크 연결을 구한 것이므로 새로운 비어있는 컴퓨터를 찾아주어야 한다. 

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    bool check[201]= {};
    stack<int> s;
    s.push(0);
    check[0] = true;
    
    while(!s.empty())
    {
        int y = s.top();
        bool Find = false;
        for(int i=0;i<n;++i)
        {
            if(computers[y][i] == 1)
            {
                if(check[i] == false)
                {
                    check[i] = true;
                    s.push(i);
                    Find = true;
                    break;
                }
            }
        }
        
        if(!Find)
        {
            // 다시 이전으로 돌아가야함
            s.pop();
            if(s.empty())
            {
                answer+=1;
                // 다음 찾아야됨
                for(int i=0;i<n;++i)
                {
                    if(check[i] == false)
                    {
                        check[i] = true;
                        s.push(i);
                        break;
                    }
                }
            }
        }
    }
    return answer;
}