프로그래머스 -level3 -네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162#

프로그래머스

정답:

#include <string>
#include <vector>
#include<iostream>
#include<queue>
using namespace std;
vector <int>q;
vector <bool>bCheck;
int func(vector<vector<int>> computers,int index,int n){
    bCheck[index]=true;
    cout<<"index:"<<index<<endl;
    for(int i=0;i<n;i++){
    if(computers[index][i]==1&&bCheck[i]==false){
           q.push_back(i);
        }
     }
   
    if(!q.empty()){
      int tmp=q[0];
      q.erase(q.begin());
      return func(computers,tmp,n);
    }
     for(int i=0;i<q.size();i++){
          cout<<"q:"<<q[i]<<endl;
     }
    return 1;
    // if(q.size()>0){
         // func(computers,q[0],n);
   //  }
    
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
     for(int i=0;i<n;i++){
         bCheck.push_back(false);
     }
    for(int i=0;i<n;i++){
        if(bCheck[i]==false){
            answer =answer+func(computers,i,n);
            }
    }
    return answer;
}

 

201008

지난번과 비슷하게 푼듯하다 

 

여기서 기존 dfs를 사용방법과 달리 stack(vector)을 같이 이용했다

개인적으로 deque를 이용하는것도 좋은 방법일듯하다 

문제를 푸는 와중엔 생각이 안나서 vector로 했는데 다음엔 deque를 이용할것이다. 

 

stack(vector) 역할은 가야할 경로의 예약이다. 

왜냐하면 

[1,1,0,0,1]

[1,1,0,0,0]

[0,0,1,0,0]

[0,0,0,1,0]

[1,0,0,0,1]

이런 경로의 경우 일반적인 dfs만 사용하면 

1번 경로와 2번경로는 이어지지만 5번 경로의 안이어 질수도 있다 그래서 

미리 내가 가야할 경로를 예약해둔다 

처음 [1,1,0,0,1] 1번 경로 

미리 vector에 

저장한다 배열은 처음이 0이므로 0으로 시작하겠다

0 ,1,4 번이 스택에 저장된다 

  for(int i=0;i<n;i++){
          if(bCheck[i]==false&&computers[index][i]==1){
               bCheck[index]=true;
              computers[index][i]=0;
              q.push_back(i);
          }
      }
  

그렇다면 

저장된 q에 

다음 func로 넘어간다 맨처음은 0이므로 패스 하겠다 

 

 while(!q.empty()){ 
         int tmp=q[0]; 
         
          q.erase(q.begin()); 
        return func(n, computers,tmp,0);  
           
      }

그러면 0번 (1번노드)는 이미 전부 지나 온 경로이므로 진행은 생략 하겠다 다음

1번을 통해 2번노드 경로로 간다. 

그러면  [1,1,0,0,0] 현재 이런식으로 되어있다

현재 0번인 1번 노드는 이미 지나온 경로이므로 stack에 쌓지 않는다.

지나온 경로는 vector<bool>bCheck로 체크 해주고 있다.

 

그러면 여기선 1번을 제외하곤 전부 0이며 또한 이미 2번노드(1번)은 들어왔기때문에 stack에 쌓지않는다.

그상태에서 현재 스택 4번을 간다. 

그러면 4번인 5번 경로를 확인한다.

[1,0,0,0,1] 여기도 마찬가지로 이미 0번(1번노드)는 지낫으며 자신을 제외하곤 없으므로 스택을 쌓지않는다.

그러면 더이상 stack이 끝나므로 

while(!q.empty()){
         int tmp=q[0];
        
          q.erase(q.begin());
        return func(n, computers,tmp,0); 
          
      }

while문은 끝난다 그러면서 return 되면서 1을 반환한다. 

다음은 메인함수에 있는

    for(int i=0;i<computers.size();i++){
        if(bCheck[i]==false){
           answer+=func(n, computers,i, 0);
            }
  }

함수에서 이미 지난 0 ,1,4 (1번,2번 5번 노드를 )제외한 다음 노드 3번 노드를 간다.

[0,0,1,0,0]

보면 q에 stack은 비어있다.

그래서 while을 입력되지 않고 

다음 while아래에 잇는 func(n, computers,q[0], count+1);  함수로 가서 다음 옆에 형제노드가 1이 존재하는지 검색한다.

여기선 자신 말곤 없으므로 1이 반환되고 종료된다.

 

그럼 다시 메인함수로 돌아오면  0 ,1,2,4 (1번,2번,3번, 5번 노드를 )제외한 다음 노드4번 노드를 간다.

[0,0,0,1,0]

마찬가지로 형재노드가 없어서 더이상 진행하지 않고 1로 반환한다 

총 합은 3으로 결정되며 경로 찾기는 종료된다.

여기서 핵심적인 부분은 stack을 이용하여 경로를 예약한다는 개념이다. 

 

정답:

#include <string>
#include <vector>
#include<iostream>
using namespace std;
void Print(vector<vector<int>> computers){
    for(int i=0;i<computers.size();i++){
        for(int j=0;j<computers[i].size();j++){
            cout<<computers[i][j]<<",";
        }
        cout<<endl;
    }
    cout<<endl;
}
vector<int> q;
vector<bool>bCheck;

int func(int n, vector<vector<int>> computers,int index,int count){
   // Print(computers);
     
       if(count>=n){
           return 1;
           }
    
      for(int i=0;i<n;i++){
          if(bCheck[i]==false&&computers[index][i]==1){
               bCheck[index]=true;
              computers[index][i]=0;
              q.push_back(i);
          }
      }
  
    
      while(!q.empty()){
         int tmp=q[0];
        
          q.erase(q.begin());
        return func(n, computers,tmp,0); 
          
      }
    
    return func(n, computers,q[0], count+1); 
    
   
    
    
}
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    
    for(int i=0;i<computers.size();i++)
    {
        bCheck.push_back(false);
    }
    
    for(int i=0;i<computers.size();i++){
        if(bCheck[i]==false){
           answer+=func(n, computers,i, 0);
            }
  }
    
    
    return answer;
}