[프로그래머스]양과늑대 C++

문제링크

내 문제 풀이 빌드업

1. 노드개수<=17. 완탐 가능한가?
2. BFS, DFS 로 백트래킹하자.
3. 노드를 재방문할 때는 양/늑대 수 변화 없음
   -> 그럼 왜 재방문? 그 노드와 연결된 자식 노드에 가려고
   -> 그럼 방문 가능한 노드를 따로 저장해서 순회하자.

첫 풀이(틀림)

코드 보기

#include <string>
#include <vector>
#include<algorithm>
#include<list>
using namespace std;

vector <vector<int>> adj;
vector <int> infos;
int maxSheep=0;
// 현재 노드, 양의 수 , 늑대의 수,남아있는 양 수, 방문여부 불린 벡터,현재 접근 가능한 노드 리스트
void dfs(int curr,int s,int w,int remainSheep,vector <bool> visited, list <int> canGo) {
    maxSheep = max(s, maxSheep);
    if (remainSheep == 0||s<=w) return;

    for (auto i : adj[curr]) {
        canGo.push_back(i);
    }
    for (list<int>::iterator next = canGo.begin(); next != canGo.end();++next) {

        if (!visited[*next]){
            if (infos[*next] == 0) { 
                visited[*next] = true;
                canGo.erase(next);
                dfs(*next, s + 1, w, remainSheep - 1,visited,canGo); 
            }
            else if (infos[*next] == 1 && s > w + 1) {
                visited[*next] = true;
                canGo.erase(next);
                dfs(*next, s, w + 1, remainSheep,visited, canGo);
            }
        }
    }
    return;
}
int solution(vector<int> info, vector<vector<int>> edges) {
    int answer = 0;
    int sheeps = 0;
    adj.resize(info.size());
    vector <bool> visited;
    list <int> cango;
    visited.resize(info.size(),false);

    infos = info;
    for (auto i:info)
    {
        if (i == 0)sheeps++;
    }
    for (auto i : edges) {
        adj[i[0]].push_back(i[1]);
    }
    for (auto i : adj[0]) {
        cango.push_back(i);
    }
    dfs(0,1,0,sheeps-1,visited,cango);
    return maxSheep;
}

시행착오

1. 방문가능한 노드 리스트인 CanGo에서 방문한 현재 노드를 빼줄때 틀림.
   List는 BidirectionalIterator이므로 순차적으로 접근한다.
   erase()로 해당 원소가 삭제되면 다음 위치를 잃어버린다.
   따라서 Iterator=List.erase(Iterator)로 리턴값을 사용해야한다.
2. 완탐문제에서 배열이나 리스트의 자료형태의 값을 독립적으로 바꾸는 작업을 수행 할 때는, 무조건 복제를 하여 독립적 리스트로써 사용하도록 주의해야한다.
3. visit 배열은 필요 없다. 어차피 자식노드만 살피고 cango에 추가하여 순회하기 때문에.

정답 풀이

#include <string>
#include <vector>
#include<algorithm>
#include<list>
using namespace std;

vector <vector<int>> adj;
vector <int> infos;
int maxSheep=0;
// 현재 노드, 양의 수 , 늑대의 수,남아있는 양 수, 현재 접근 가능한 노드 리스트
void dfs(int curr,int s,int w,int remainSheep, list <int> canGo) {
  if (infos[curr] == 1) {
      w++;
      if (s <= w)return;
  }
  else {
      s++;
      remainSheep--;
      maxSheep = max(s, maxSheep);
      // 트리에 양이 남아있지 않으면 그 이후 노드를 볼 필요가 없다.
      if(remainSheep==0)return;
  }
  list <int> newCanGo(canGo);

  for (auto i : adj[curr]) 
      newCanGo.emplace_back(i);
   newCanGo.remove(curr);
   for (auto next : newCanGo)
       dfs(next, s, w, remainSheep, newCanGo);
  return;
}
int solution(vector<int> info, vector<vector<int>> edges) {
  int answer = 0;
  int sheeps = 0;
  adj.resize(info.size());
  list <int> cango;

  infos = info;
  for (auto i:info)
  {
      if (i == 0)sheeps++;
  }
  for (auto i : edges) {
      adj[i[0]].push_back(i[1]);
  }
  dfs(0,0,0,sheeps,cango);
  return maxSheep;
}

다른 사람들의 해결 방법

• 양방향 그래프
  -> 불필요한 무한 재귀호출 가능성 有

• 삼차원 visited 배열 [현재 노드,양의수, 늑대의 수].
  visit[A][B][C] = true : A번 노드에 양을 B마리 늑대를 C마리를 데리고 방문한 적이 있다는 뜻. 참고링크
  ->직접 해보진않았지만 우연히 겹치는 같은 양의수,늑대의 수 경우가 있으면 우짜지?

  • 비슷한 풀이로 비트마스킹을 이용하여 방문 상태 저장
    01789 정점 방문 시 1110000011(2)=899로 나타내어 visited[899]=true. 즉 2^n개 의 상태로 관리.
    -> PS할때 공간 복잡도 계산을 잘 안해서 이 경우 되는지 가늠이 잘 안간다ㅜ.

• 갈 수 있는 정점을 따로 담아서 재귀호출
  ->내가 푼 방법

• dp로 n마리 모은 경로를 바탕으로 n+1 마리를 모을 수 있는 경우 구하기 반복 참고링크